Sorting Intuition
Quick reference
| Merge Sort | O(n log n) |
| Quick Sort | O(n log n) average, O(n²) worst case |
| Heap Sort (preview — built in Phase 5) | O(n log n) |
Sorting is a one-time investment. You pay a cost one time to put the data in order. After that, many questions that are usually expensive become cheap. Examples are: find the median, check for duplicates, and merge two lists. There are several strategies for the sort itself. They make different trade-offs.
Merge Sort splits the array in half. It sorts each half with recursion. Then it merges the two sorted halves together. This is the same divide-and-conquer shape as pow(x, n) from Recursion Basics, but for sorting instead of exponentiation. Quick Sort is different. It picks a pivot value. It partitions the array into "less than the pivot" and "greater than the pivot" in place. Then it recurses into each side. A third strategy is Heap Sort. It pulls out the current smallest (or largest) remaining element one at a time with a heap. But a heap is a structure that this curriculum has not built yet. The heap is the full subject of Phase 5. So this topic shows Heap Sort only by name and comparison. This topic does not implement Heap Sort. This is intentional, not a gap. You cannot build the engine of Heap Sort before you build the engine itself.
Two sorting strategies
// The shared divide-and-conquer skeleton (the same shape as Recursion Basics):
function sort(arr):
if arr is very small (0 or 1 elements): // base case: already sorted
return arr
... split or partition the problem ...
... sort the smaller piece or pieces with recursion ...
... combine the results ...Merge Sort — divide, recursively sort, merge
function mergeSort(arr):
if length(arr) <= 1:
return arr // base case: 0 or 1 elements is already sorted
mid = length(arr) // 2
left = mergeSort(arr[0:mid]) // sort the left half with recursion
right = mergeSort(arr[mid:]) // sort the right half with recursion
return merge(left, right)
function merge(left, right):
result = []
i, j = 0, 0
while i < length(left) and j < length(right):
if left[i] <= right[j]: // <= (not <) keeps equal elements in their
result.append(left[i]) // original order. This is what "stable" means.
i += 1
else:
result.append(right[j])
j += 1
result.append(remaining elements of left) // the side that has elements left
result.append(remaining elements of right)
return resultQuick Sort — pick a pivot, partition, recurse
function quickSort(arr, lo, hi):
if lo >= hi:
return // base case: 0 or 1 elements is already sorted
pivotIndex = partition(arr, lo, hi)
quickSort(arr, lo, pivotIndex - 1) // recurse into the left of the pivot
quickSort(arr, pivotIndex + 1, hi) // recurse into the right of the pivot
function partition(arr, lo, hi):
pivot = arr[hi] // Use the last element as the pivot (the simplest choice).
boundary = lo // Each element before 'boundary' is < pivot.
for i from lo to hi - 1:
if arr[i] < pivot:
swap(arr[i], arr[boundary])
boundary += 1
swap(arr[boundary], arr[hi]) // Put the pivot in its final sorted position.
return boundary"Stable" means that equal elements keep their original relative order after the sort. This is important when you sort records (for example, people) by one field (for example, age) and you want the ties to stay in their original order.
| Operation | Time | Space | Why |
|---|---|---|---|
| Merge Sort | O(n log n) | O(n) | There are log n levels of splitting and O(n) work to merge at each level. But the merge needs a separate output array. This is the O(n) extra space. |
| Quick Sort | O(n log n) average, O(n²) worst case | O(log n) average, O(n) worst case | The partition is in place (no extra array). The space is the recursion stack, one frame for each level. A pivot choice that is always unlucky can make one side of each partition empty. Then log n levels of recursion become n levels. This same bad input drives the time to O(n²) and the recursion stack to O(n). |
| Heap Sort (preview — built in Phase 5) | O(n log n) | O(1) | To pull the current smallest or largest element from a heap costs O(log n) for each pull, and there are n pulls in total. It needs no extra array. But it needs a working heap first. |
Quick Sort's O(n²) worst case on sorted input
If you always pick arr[hi] as the pivot on an already-sorted array, each partition puts zero elements on one side and all other elements on the other side. The recursion does not divide the problem in half. It reduces the problem by one each time. This gives O(n) levels instead of O(log n), which is O(n²) in total. Pick a random pivot, or the median of a few sample elements. This makes the unlucky case very unlikely instead of guaranteed by a predictable input.
Merge Sort's O(n) extra space is a real cost
Merge Sort needs a second array to merge into. This is not free at a large scale. For very large datasets, two times the memory can matter more than the time complexity. Then the O(log n) space of Quick Sort (only the recursion stack) or the O(1) space of Heap Sort can be the deciding factor, even though all three share the same O(n log n) time.
Assuming a sort is stable when it is not
The swap-based partition of Quick Sort can reorder equal elements. Quick Sort is not stable by default. Think about code that sorts a list of records by department and expects people in the same department to keep their original order (perhaps already sorted by name). If the sort is not stable, it can scramble that second order with no error. Check which guarantee the sort of your language or library makes. Do not assume.
Sorting records with the wrong or an unstable comparator
A comparator that is not consistent is a problem. For example, one that sometimes says A < B and sometimes says B < A for the same pair. Or one that does not handle equal elements in a predictable way. Such a comparator can make different sorting algorithms give different (and sometimes wrong) results on the same data. All algorithms assume that the comparator defines one consistent order to work toward.
Sign in to mark problems done — progress syncs across devices.