Sorts of all sorts

Sorts.md

Sorts

Bubble sort

Complexity	Space	Stable
O(n^2)	O(1)	Yes
Until array is sorted compares adjacent pairs and swaps them if they are in the wrong order.
+ Easy to implement

Selection sort

Complexity	Space	Stable
O(n^2)	O(1)	No
For each index in array find smallest and insert on index.
+ Use fewer swaps
- Not stable

Insertion sort

Complexity	Space	Stable
O(n^2)	O(1)	Yes
Scan array and each time insert the item in the unordered sequence into its correct position.
+ Good for partitaly sorted data.

Shell sort

Complexity	Space	Stable
<O(n^2)	O(1)	No
Simple extension of insertion sort that gains speed by allowing exchanges of array entries that are far apart.
+ Sligthly faster than Insertion sort.

Merge sort

Complexity	Space	Stable
O(n log(n))	O(n)	Yes
It divides input array in two halves, calls itself for the two halves and then merges the two sorted halves.
+ Insertion sort cut off
+ Parallelisable
+ Can be used for external sorting
- Memory and recursion stack

Quick sort

Complexity	Space	Stable
~O(n log(n))	O(1)	No
Partition array into two subrarrays such that left is less than pivot and right is more.
+ Insertion sort cut off
+ Parallelisable
+ Can be used for external sorting
+ 3 way for equal keys (strings)
- n^2 worst case

Heap sort

Complexity	Space	Stable
O(n log(n))	O(1)	No
It breaks into two phases: heap construction, where we reorganize the original array into a heap, and the sortdown, where we pull the items out of the heap in decreas- ing order to build the sorted result.
- Big constant factors

// Heap construction
for i in stride(from: count / 2, through: 0, by: -1) {
    sink(i, to: count)
}
// Sortdown
for i in stride(from: count - 1, to: 0, by: -1) {
    swapAt(0, i)
    sink(0, to: i)
}

Key-indexed counting

Complexity	Space	Stable
O(n)	O(n)	Yes

// Compute frequency counts:
for n in input { count[n] += 1 }
// Transform counts to indices
for i in 0..<count.count - 1 {
    count[i + 1] += count[i]
}
// Distribute data
for n in input {
    let position = count[n]
    aux[position] = string
    count[n] += 1
}

LSD, Radix Sort

Complexity	Space	Stable
O(nw)	O(n)	Yes
w - is a key length.
Repeat key-indexed counting for each character / digit.
+ Short fixed-length strings

External Sort

Complexity	Space	Stable
O(logk(N/M))	O(n)	Yes
Sort chunks that fits into memory with merge sort or quick sort. Merge chunks using min heap, replace values in heap from chunk which corresponds to last emitted value. Or by binary merging chunks by two.