# Array sort algorithms in Python

# Array sort algorithms in Python

## Definitions

**What is stable sorting?**

A sorting algorithm is said to be stable if two objects with equal keys appear in the same order in sorted output as they appear in the input array to be sorted.

**What is in-place sorting?**

An in-place sorting algorithm uses constant extra space even for producing the output (modifies the given array only). For example, Insertion Sort and Selection Sorts are in-place sorting algorithms and a typical implementation of Merge Sort is not in-place.

**What are Internal and External Sortings?**

When all data that needs to be sorted cannot be placed in-memory at a time, the sorting is called external sorting. External Sorting is used for massive amount of data. Merge Sort and its variations are typically used for external sorting. Some extrenal storage like hard-disk, CD, etc is used for external storage.

When all data is placed in-memory, then sorting is called internal sorting.

## Insertion Sort

Insertion sort is a simple sorting algorithm that is relatively efficient for small lists and mostly sorted lists, and is often used as part of more sophisticated algorithms.

Class | Sorting algorithm |

Data structure | Array |

Worst-case performance | О(n2) comparisons, swaps |

Best-case performance | O(n) comparisons, O(1) swaps |

Average performance | О(n2) comparisons, swaps |

Worst-case space complexity | О(n) total, O(1) auxiliary |

Boundary Cases | Insertion sort takes maximum time to sort if elements are sorted in reverse order. And it takes minimum time (Order of n) when elements are already sorted. |

Algorithmic Paradigm | Incremental Approach |

Sorting In Place | Yes |

Stable | Yes |

Online | Yes |

Uses | Insertion sort is used when number of elements is small. It can also be useful when input array is almost sorted, only few elements are misplaced in complete big array. |

## Merge sort

Class | Sorting algorithm |

Data | structure Array |

Worst-case performance | O(n log n) |

Best-case performance | O(n log n) typical, O(n) natural variant |

Average performance | O(n log n) |

Worst-case space complexity | О(n) total, O(n) auxiliary |

Algorithmic Paradigm | Divide and Conquer |

Sorting In Place | No in a typical implementation |

Stable | Yes |

## Quick Sort

Class | Sorting algorithm | |

Worst-case performance | O(n2) | |

Best-case performance | O(n log n) (simple partition) | or O(n) (three-way partition and equal keys) |

Average performance | O(n log n) | |

Worst-case space complexity | O(n) auxiliary (naive) | O(log n) auxiliary (Sedgewick 1978) |