Sorting Algorithms
Algorithms & Complexity · Coding Fundamentals track
8 min read
In this module
Putting Things in Order
Sorting (arranging elements in a defined order) is one of the most studied problems in computer science. Knuth's The Art of Computer Programming reports that 1960s computer manufacturers reckoned more than a quarter of their machines' running time went on sorting. Sorted data enables binary search, simplifies duplicate detection, makes merging easier, and improves human readability.
Bubble Sort: The Simplest Sort
Bubble sort walks the list comparing adjacent elements and swapping them if they're out of order. Each pass, the largest unsorted element "bubbles up" to its correct position.
function bubble_sort(list) { n = length(list) for i = 0 to n - 2 { for j = 0 to n - 2 - i { if list[j] > list[j+1] { swap(list[j], list[j+1]) } } }}Time complexity: O(n^2). Two nested loops, each up to n iterations. This version always does every pass, even on a list that's already sorted. Add a flag that stops as soon as a pass makes no swaps and a sorted list costs one O(n) pass instead, which is the version the table at the end of this lesson assumes.
Bubble sort is simple to understand and implement, but it crawls on large datasets. Treat it as a teaching tool, not a production algorithm.
Selection Sort
Selection sort finds the smallest element and puts it first, then finds the next smallest and puts it second, and so on.
function selection_sort(list) { n = length(list) for i = 0 to n - 2 { min_index = i for j = i + 1 to n - 1 { if list[j] < list[min_index] { min_index = j } } swap(list[i], list[min_index]) }}Time complexity: O(n^2). Like bubble sort, it uses nested loops. The win is that it performs at most n swaps, making it the preferable pick when writes are expensive.
Insertion Sort
Insertion sort builds the sorted array one element at a time by inserting each new element into its correct position among the already-sorted elements.
function insertion_sort(list) { for i = 1 to length(list) - 1 { key = list[i] j = i - 1 while j >= 0 and list[j] > key { list[j+1] = list[j] j = j - 1 } list[j+1] = key }}Time complexity: O(n^2) worst case, but O(n) on already-sorted or nearly-sorted data. That makes insertion sort excellent for small datasets and for slotting new elements into an already-sorted list. Many practical sorting algorithms call insertion sort as a subroutine on small partitions.
Simple sorting algorithms like bubble sort, selection sort, and insertion sort are all O(n^2). Easy to understand. Impractical at scale. Efficient sorting demands a fundamentally different approach.
Merge Sort: Divide and Conquer
Merge sort uses a strategy called divide and conquer: split the array in half, recursively sort each half, then merge the two sorted halves together.
function merge_sort(list) { if length(list) <= 1 { return list // base case: already sorted }
mid = length(list) / 2 left = merge_sort(list[0..mid]) // sort left half right = merge_sort(list[mid..end]) // sort right half return merge(left, right) // merge the sorted halves}
function merge(left, right) { result = [] i = 0, j = 0 while i < length(left) and j < length(right) { if left[i] <= right[j] { append result, left[i] i = i + 1 } else { append result, right[j] j = j + 1 } } // append any remaining elements append result, left[i..end] append result, right[j..end] return result}Time complexity: O(n log n) in all cases. The array is split log n times, and each level of merging takes O(n) work.
Space complexity: O(n). The merge step needs a temporary array.
Merge sort is stable (equal elements keep their relative order) and guaranteed O(n log n), which makes it a reliable choice for general-purpose sorting.
Quicksort
Quicksort picks a pivot element, partitions the array into elements less than the pivot and elements greater than the pivot, and recursively sorts each partition.
function quicksort(list, low, high) { if low < high { pivot_index = partition(list, low, high) quicksort(list, low, pivot_index - 1) quicksort(list, pivot_index + 1, high) }}Time complexity: O(n log n) average case, O(n^2) worst case (when the pivot is always the smallest or largest element). Random pivot selection mitigates this.
Space complexity: O(log n) for the recursion stack (in-place partitioning).
In practice, quicksort often beats merge sort thanks to better cache locality and lower constant factors, even though its worst case is uglier.
Here are all five, each counting its comparisons on the same 1,000 shuffled numbers, then on 1,000 numbers that are already sorted. Before you run it, guess which algorithms barely break a sweat on sorted input and which one collapses.
Quicksort with the last element as its pivot hits its O(n^2) worst case on sorted input, because every partition splits off just one element. Random pivot selection is the usual fix.
Choosing the Right Sort
| Algorithm | Best | Average | Worst | Space | Stable? |
|---|---|---|---|---|---|
| Bubble sort | O(n) | O(n^2) | O(n^2) | O(1) | Yes |
| Selection sort | O(n^2) | O(n^2) | O(n^2) | O(1) | No |
| Insertion sort | O(n) | O(n^2) | O(n^2) | O(1) | Yes |
| Merge sort | O(n log n) | O(n log n) | O(n log n) | O(n) | Yes |
| Quicksort | O(n log n) | O(n log n) | O(n^2) | O(log n) avg | No |
Most standard library sort functions use a hybrid approach: quicksort for large partitions, insertion sort for small partitions, and sometimes merge sort for stability guarantees. Python uses Powersort (a Timsort derivative, itself a hybrid of merge sort and insertion sort). C++ often uses Introsort, a quicksort that falls back to heapsort when recursion gets too deep.
To see the table in action, run the stepper below on its 12 values with each algorithm in turn, using the drop-down, and keep an eye on the comparison and swap counters. Merge sort and quicksort make the fewest comparisons, but on an array this small insertion sort isn't far behind them. That's exactly why the hybrid sorts below hand small partitions to insertion sort.
Algorithm Visualizer
The best and worst cases in the table depend on the input, so try a sorted one too. On the stepper below, insertion sort makes one comparison per element and is done. Quicksort is a different story: this version always picks the last element as its pivot, so on sorted input every split leaves nothing on one side and it slides to its O(n^2) worst case: 66 comparisons, as many as bubble sort. That's why real implementations choose pivots more carefully.
Algorithm Visualizer
The theoretical lower bound for comparison-based sorting is O(n log n). You can't sort faster than this by comparing elements pairwise. Non-comparison sorts like counting sort and radix sort can beat the bound under specific conditions, but they need special properties of the data (such as bounded integer values).