Sort 9 values between 1 and 99 without comparing them across the whole array. Split the value range into 4 equal buckets, drop each value into the bucket its value falls in, sort each small bucket on its own, then read the buckets out in order.
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