Sorting Algorithms: Comparison, Non-Comparison, Stability, and Hybrids

Sorting rearranges a collection of items into a monotonic order (ascending or descending). It is a fundamental building block for binary search, database indexing (B-Tree splits), join processing (Sort-Merge Joins), and data deduplication.

⚡ Quick Dive

Master Sorting Algorithms Comparison Matrix

Algorithm Best Time Average Time Worst Time Space Overhead Stable? In-Place? Paradigm
Insertion Sort $O(n)$ $O(n^2)$ $O(n^2)$ $O(1)$ ✅ ✅ Incremental (Adaptive)
Selection Sort $O(n^2)$ $O(n^2)$ $O(n^2)$ $O(1)$ ❌ ✅ Selection
Bubble Sort $O(n)$ $O(n^2)$ $O(n^2)$ $O(1)$ ✅ ✅ Exchange
Merge Sort $O(n \log n)$ $O(n \log n)$ $O(n \log n)$ $O(n)$ ✅ ❌ Divide & Conquer
QuickSort $O(n \log n)$ $O(n \log n)$ $O(n^2)$ $O(\log n)$ (Stack) ❌ ✅ Divide & Conquer
HeapSort $O(n \log n)$ $O(n \log n)$ $O(n \log n)$ $O(1)$ ❌ ✅ Selection (Binary Heap)
Counting Sort $O(n + k)$ $O(n + k)$ $O(n + k)$ $O(k)$ ✅ ❌ Non-Comparison (Integer keys)
Radix Sort $O(d \cdot (n + k))$ $O(d \cdot (n + k))$ $O(d \cdot (n + k))$ $O(n + k)$ ✅ ❌ Non-Comparison (Digits)
Timsort (Hybrid) $O(n)$ $O(n \log n)$ $O(n \log n)$ $O(n)$ ✅ ❌ Insertion + Merge (Production)

📖 Extended Guide

1. Stability in Sorting

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

Input:  [ (Alice, Grade: B), (Bob, Grade: A), (Charlie, Grade: B) ]
                                ▲                      ▲
Stable Sort by Grade:
Output: [ (Bob, A), (Alice, B), (Charlie, B) ]  ◄── Relative order of Alice and Charlie preserved

Unstable Sort by Grade:
Output: [ (Bob, A), (Charlie, B), (Alice, B) ]  ◄── Relative order swapped

Stability is critical in multi-key database sorting (e.g. sort by Date, then sort by Department).

2. High-Performance QuickSort: Hoare vs. Lomuto Partitioning

QuickSort operates by choosing a pivot, partitioning the array around the pivot, and recursively sorting subarrays.

  • Lomuto Partitioning: Simpler to code; scans with single forward pointer. Performs more swaps and degrades to $O(n^2)$ on arrays with all equal keys.
  • Hoare Partitioning: Scans inward from both ends; performs three times fewer swaps on average and handles duplicate keys efficiently.
package main

import "fmt"

// QuickSort using Hoare Partition Scheme
func QuickSort(arr []int, low, high int) {
	if low < high {
		p := partition(arr, low, high)
		QuickSort(arr, low, p)
		QuickSort(arr, p+1, high)
	}
}

func partition(arr []int, low, high int) int {
	pivot := arr[low + (high-low)/2] // Avoid worst-case on sorted inputs
	i := low - 1
	j := high + 1

	for {
		for {
			i++
			if arr[i] >= pivot {
				break
			}
		}
		for {
			j--
			if arr[j] <= pivot {
				break
			}
		}
		if i >= j {
			return j
		}
		arr[i], arr[j] = arr[j], arr[i]
	}
}

func main() {
	nums := []int{38, 27, 43, 3, 9, 82, 10}
	QuickSort(nums, 0, len(nums)-1)
	fmt.Println("Sorted:", nums)
}

3. Merge Sort (Guaranteed $O(n \log n)$ Stable Sorting)

Merge Sort divides the array into halves, recursively sorts them, and merges the sorted halves:

Divide:                [ 38, 27, 43, 3 ]
                      /                 \
               [ 38, 27 ]             [ 43, 3 ]
               /        \             /       \
            [ 38 ]    [ 27 ]       [ 43 ]    [ 3 ]
Merge:         \        /             \       /
               [ 27, 38 ]             [ 3, 43 ]
                      \                 /
                    [ 3, 27, 38, 43 ]

Merge Sort is ideal for sorting Linked Lists (because merging linked lists requires $O(1)$ auxiliary memory without array copying) and External Sorting (sorting terabytes of data stored on disks that don't fit in RAM).

4. Non-Comparison Linear Sorts: Counting Sort

When input keys are integers bounded within range $[0, k]$, Counting Sort achieves $O(n + k)$ linear time by tallying frequencies:

func CountingSort(arr []int, k int) []int {
	count := make([]int, k+1)
	output := make([]int, len(arr))

	// 1. Store frequencies
	for _, v := range arr {
		count[v]++
	}

	// 2. Accumulate prefix sums (positions)
	for i := 1; i <= k; i++ {
		count[i] += count[i-1]
	}

	// 3. Build output backward to maintain stability
	for i := len(arr) - 1; i >= 0; i-- {
		val := arr[i]
		output[count[val]-1] = val
		count[val]--
	}

	return output
}

5. Production Hybrid Sorts: Timsort & IntroSort

Modern programming language standard libraries do not use pure theoretical sorting algorithms:

  • Timsort (Python list.sort(), Java Arrays.sort(), Rust): Scans for existing natural sorted runs, extends short runs with Insertion Sort, and merges them using a balanced stack. Achieves $O(n)$ best-case time on real-world partially sorted data while maintaining $O(n \log n)$ worst-case and stability.
  • IntroSort (C++ std::sort()): Begins with QuickSort for raw speed, monitors recursion depth, and switches to HeapSort if depth exceeds $2\log_2 n$ (preventing $O(n^2)$ worst cases), switching to Insertion Sort for tiny subarrays ($n < 16$).
⌂ All Guides