2017, Dec 22

# 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) 