Timsort, the sort behind Python and Java's object sort. Real data usually contains stretches that are already ascending. Find each such run, extend any run shorter than 4 with insertion sort, then merge neighbouring runs until one remains.
The code
More Sorts, in Python
def shell_sort(a):
gap = len(a) // 2
while gap > 0: # insertion sort with a stride, halving to 1
for i in range(gap, len(a)):
j = i
while j >= gap and a[j - gap] > a[j]:
swap(a, j - gap, j); j -= gap
gap //= 2
def quick_sort3(a, lo, hi): # Dijkstra's three-way partition
if lo >= hi: return
pivot = a[lo]
lt = lo; i = lo + 1; gt = hi
while i <= gt:
if a[i] < pivot: # grow the < zone
swap(a, lt, i); lt += 1; i += 1
elif a[i] > pivot: # grow the > zone; look at the new a[i] next
swap(a, i, gt); gt -= 1
else: # equal: it stays in the middle
i += 1
quick_sort3(a, lo, lt - 1); quick_sort3(a, gt + 1, hi) # the equal zone is never touched again
def bucket_sort(a, buckets):
bucket = [[] for _ in range(buckets)]
for v in a: bucket[v * buckets // 100].append(v) # scatter: the value range split evenly
for b in bucket: b.sort() # each bucket is small: insertion sort
k = 0
for b in bucket: # gather in bucket order
for v in b: a[k] = v; k += 1
def tim_sort(a, min_run):
runs = []
i = 0
while i < len(a):
end = i + 1
while end < len(a) and a[end - 1] <= a[end]: # a natural ascending run
end += 1
end = max(end, min(i + min_run, len(a))) # too short: extend it
insertion_sort(a, i, end - 1); runs.append(range(i, end))
i = end
while len(runs) > 1: runs = merge_neighbours(a, runs) # bottom-up merges, like merge sort
def intro_sort(a):
sort(a, 0, len(a) - 1, 2 * log2(len(a))) # the depth budget
def sort(a, lo, hi, depth):
if hi - lo + 1 <= SMALL: # tiny range: insertion sort wins
insertion_sort(a, lo, hi); return
if depth == 0: # budget spent: quicksort is degrading
heap_sort(a, lo, hi); return
p = partition(a, lo, hi) # Lomuto, last value as pivot
sort(a, lo, p - 1, depth - 1); sort(a, p + 1, hi, depth - 1)
def randomized_quick_sort(a, lo, hi, rng):
if lo >= hi: return
swap(a, rng.randint(lo, hi), hi) # a random pivot moves to the end
p = partition(a, lo, hi) # then the usual Lomuto partition
randomized_quick_sort(a, lo, p - 1, rng); randomized_quick_sort(a, p + 1, hi, rng)
# expected depth O(log n) on every input
More Sorts, in JavaScript
function shellSort(a) {
let gap = Math.floor(a.length / 2);
while (gap > 0) { // insertion sort with a stride, halving to 1
for (let i = gap; i < a.length; i++) {
let j = i;
while (j >= gap && a[j - gap] > a[j]) { swap(a, j - gap, j); j -= gap; }
}
gap = Math.floor(gap / 2);
}
}
function quickSort3(a, lo, hi) { // Dijkstra's three-way partition
if (lo >= hi) return;
const pivot = a[lo];
let lt = lo;
let i = lo + 1;
let gt = hi;
while (i <= gt) {
if (a[i] < pivot) swap(a, lt++, i++); // grow the < zone
else if (a[i] > pivot) swap(a, i, gt--); // grow the > zone; look at the new a[i] next
else i++; // equal: it stays in the middle
}
quickSort3(a, lo, lt - 1); quickSort3(a, gt + 1, hi); // the equal zone is never touched again
}
function bucketSort(a, buckets) {
const bucket = Array.from({ length: buckets }, () => []);
for (const v of a) bucket[Math.floor((v * buckets) / 100)].push(v); // scatter: the value range split evenly
for (const b of bucket) b.sort((x, y) => x - y); // each bucket is small: insertion sort
let k = 0;
for (const b of bucket) for (const v of b) a[k++] = v; // gather in bucket order
}
function timSort(a, minRun) {
let runs = [];
let i = 0;
while (i < a.length) {
let end = i + 1;
while (end < a.length && a[end - 1] <= a[end]) end++; // a natural ascending run
end = Math.max(end, Math.min(i + minRun, a.length)); // too short: extend it
insertionSort(a, i, end - 1); runs.push([i, end]);
i = end;
}
while (runs.length > 1) runs = mergeNeighbours(a, runs); // bottom-up merges, like merge sort
}
const introSort = (a) => sort(a, 0, a.length - 1, 2 * log2(a.length)); // the depth budget
function sort(a, lo, hi, depth) {
if (hi - lo + 1 <= SMALL) { insertionSort(a, lo, hi); return; } // tiny range: insertion sort wins
if (depth === 0) { heapSort(a, lo, hi); return; } // budget spent: quicksort is degrading
const p = partition(a, lo, hi); // Lomuto, last value as pivot
sort(a, lo, p - 1, depth - 1); sort(a, p + 1, hi, depth - 1);
}
function randomizedQuickSort(a, lo, hi, rng) {
if (lo >= hi) return;
swap(a, rng.nextInt(lo, hi + 1), hi); // a random pivot moves to the end
const p = partition(a, lo, hi); // then the usual Lomuto partition
randomizedQuickSort(a, lo, p - 1, rng); randomizedQuickSort(a, p + 1, hi, rng);
} // expected depth O(log n) on every input
More Sorts, in Kotlin
fun shellSort(a: IntArray) {
var gap = a.size / 2
while (gap > 0) { // insertion sort with a stride, halving to 1
for (i in gap until a.size) {
var j = i
while (j >= gap && a[j - gap] > a[j]) { swap(a, j - gap, j); j -= gap }
}
gap /= 2
}
}
fun quickSort3(a: IntArray, lo: Int, hi: Int) { // Dijkstra's three-way partition
if (lo >= hi) return
val pivot = a[lo]
var lt = lo; var i = lo + 1; var gt = hi
while (i <= gt) {
when {
a[i] < pivot -> swap(a, lt++, i++) // grow the < zone
a[i] > pivot -> swap(a, i, gt--) // grow the > zone; look at the new a[i] next
else -> i++ // equal: it stays in the middle
}
}
quickSort3(a, lo, lt - 1); quickSort3(a, gt + 1, hi) // the equal zone is never touched again
}
fun bucketSort(a: IntArray, buckets: Int) {
val bucket = List(buckets) { mutableListOf<Int>() }
for (v in a) bucket[v * buckets / 100] += v // scatter: the value range split evenly
for (b in bucket) b.sort() // each bucket is small: insertion sort
var k = 0
for (b in bucket) for (v in b) a[k++] = v // gather in bucket order
}
fun timSort(a: IntArray, minRun: Int) {
var runs = mutableListOf<IntRange>()
var i = 0
while (i < a.size) {
var end = i + 1
while (end < a.size && a[end - 1] <= a[end]) end++ // a natural ascending run
end = max(end, min(i + minRun, a.size)) // too short: extend it
insertionSort(a, i, end - 1); runs += i until end
i = end
}
while (runs.size > 1) runs = mergeNeighbours(a, runs) // bottom-up merges, like merge sort
}
fun introSort(a: IntArray) = sort(a, 0, a.size - 1, 2 * log2(a.size)) // the depth budget
fun sort(a: IntArray, lo: Int, hi: Int, depth: Int) {
if (hi - lo + 1 <= SMALL) { insertionSort(a, lo, hi); return } // tiny range: insertion sort wins
if (depth == 0) { heapSort(a, lo, hi); return } // budget spent: quicksort is degrading
val p = partition(a, lo, hi) // Lomuto, last value as pivot
sort(a, lo, p - 1, depth - 1); sort(a, p + 1, hi, depth - 1)
}
fun randomizedQuickSort(a: IntArray, lo: Int, hi: Int, rng: Random) {
if (lo >= hi) return
swap(a, rng.nextInt(lo, hi + 1), hi) // a random pivot moves to the end
val p = partition(a, lo, hi) // then the usual Lomuto partition
randomizedQuickSort(a, lo, p - 1, rng); randomizedQuickSort(a, p + 1, hi, rng)
} // expected depth O(log n) on every input