09 Sorting Algorithms

Foundations of Sorting

Sorting rearranges a collection into a specified order, such as ascending numerical order or alphabetical order. A correct sort must produce an ordered sequence containing exactly the same elements as the input: it changes positions, not the collection's contents.

Sorting supports searching, grouping records, removing duplicate values, and producing ordered reports. When evaluating an algorithm, consider four main questions:

• Correctness: Is the result ordered according to the comparison rule and a permutation of the input?

• Running time: How does the number of operations grow as the input size $n$ increases?

• Extra space: How much memory beyond the input collection is required?

• Stability: Do equal-key records retain their original relative order?

A permutation contains exactly the same elements as the original collection, possibly in a different arrangement. This requirement distinguishes sorting from operations that add, remove, or alter data.

The notation $O(f(n))$ describes an asymptotic upper-growth category, while $\Theta(f(n))$ describes a tight asymptotic growth category. The notation $\Omega(f(n))$ describes an asymptotic lower bound. These notations help compare how algorithms scale, although constant factors and memory-access patterns can affect practical speed.

Takeaway: A sorting algorithm is judged not only by whether it produces the right order, but also by its time, memory use, stability, and behavior on particular input patterns.

Stability and Comparison Limits

When records have keys, equal keys may still carry meaningful information. Stability preserves the original relative order of records whose keys compare equal.

For example, consider the records $(\text{Ana},90)$, $(\text{Ben},75)$, and $(\text{Cara},90)$. Sorting by score with a stable algorithm produces $(\text{Ben},75)$, $(\text{Ana},90)$, and $(\text{Cara},90)$. Ana remains before Cara because that was their original order among the records with score $90$.

Stability matters in multi-field sorting. One approach is to sort records by last name and then stably sort them by department. Within each department, equal-department records retain their alphabetical last-name order.

Stability is a property of an implementation, not merely an algorithm's name. An implementation can sometimes be made stable by tracking original positions when keys are equal, but that bookkeeping may require additional memory.

Comparison-Based Sorting determines order by asking questions such as whether one element is less than another. For arbitrary input, the worst-case lower bound is $\Omega(n \log n)$. Counting sort and radix sort can avoid this comparison lower bound by using assumptions about the keys, but those methods are outside the scope of this guide.

Takeaway: Stability is essential when equal-key records have a meaningful prior order, while the comparison model explains why general-purpose comparison sorts cannot guarantee sub-$n \log n$ worst-case time.

Elementary Sorting Algorithms

The elementary algorithms differ mainly in how they build the sorted region and how much work they repeat.

Selection sort maintains a sorted prefix. At position $i$, it scans positions $i$ through $n-1$, finds the smallest remaining element, and swaps it into position $i$. For the input $[5,3,4,1,2]$, the sorted prefix grows as $[1]$, then $[1,2]$, then $[1,2,3]$, and finally $[1,2,3,4,5]$.

It performs $\Theta(n^2)$ comparisons in every case because it scans the remaining unsorted region even when the input is already ordered. It performs only $O(n)$ swaps, which can be useful when writes are expensive. The standard version is in-place but not stable.

Insertion sort also grows a sorted prefix, but it takes the next element and shifts larger elements right until the element fits. For $[5,2,4,6,1,3]$, the sorted prefixes are $[5]$, $[2,5]$, $[2,4,5]$, $[2,4,5,6]$, $[1,2,4,5,6]$, and $[1,2,3,4,5,6]$.

Its best-case time is $O(n)$ when the input is already sorted or nearly sorted. Its average- and worst-case time is $O(n^2)$, with reverse order producing a typical worst case. Array implementations use $O(1)$ extra space and are stable when equal elements are not shifted past one another.

Bubble sort repeatedly compares adjacent elements and swaps them when they are strictly out of order. During a pass over $[5,1,4,2]$, the value $5$ moves rightward through successive swaps until the array becomes $[1,4,2,5]$.

With an early-exit check that stops after a pass with no swaps, bubble sort has best-case time $O(n)$, average-case time $O(n^2)$, and worst-case time $O(n^2)$. It uses $O(1)$ extra space and can be stable. In practice, insertion sort generally performs better on the same class of small or partially sorted inputs.

Takeaway: Selection sort minimizes comparisons' dependence on input order and uses few swaps; insertion sort is strong on nearly sorted data; bubble sort is mainly valuable for instruction and simple demonstrations.

Divide-and-Conquer Sorting

Divide-and-conquer algorithms solve sorting problems by breaking them into smaller parts, solving those parts, and combining their results.

Merge sort divides the input into two halves, recursively sorts each half, and merges the sorted halves. For $[8,3,7,4,9,2]$, the halves $[8,3,7]$ and $[4,9,2]$ become $[3,7,8]$ and $[2,4,9]$, which merge to form $[2,3,4,7,8,9]$.

The recurrence is

The recursive calls account for the first term, and merging accounts for $\Theta(n)$. Thus, merge sort has $O(n \log n)$ best-, average-, and worst-case time. It is stable when the merge chooses the left item first on equal keys, but an array implementation usually requires $O(n)$ extra space. Its structure is well suited to linked lists and external sorting.

Quicksort selects a pivot, partitions the array so smaller values lie on one side and larger values on the other, and recursively sorts the two partitions. For the input $[8,3,7,4,9,2,5]$ with pivot $5$, the values less than the pivot are $[3,4,2]$, the pivot is $[5]$, and the values greater than the pivot are $[8,7,9]$.

Partitioning a subarray of size $n$ takes $\Theta(n)$ time. Balanced partitions produce the recurrence

whereas repeatedly choosing the smallest or largest element produces

Quicksort is usually in-place apart from recursion-stack space and is often fast in practice. Its expected stack space is $O(\log n)$ for balanced partitions but can reach $O(n)$ in the worst case. The standard in-place form is not stable. Randomized pivots, median-based choices, and three-way partitioning can reduce the effects of poor pivots, especially when many values are equal.

Takeaway: Merge sort offers predictable $O(n\log n)$ performance and stability at the cost of auxiliary storage; quicksort is often faster and mostly in-place but requires careful pivot handling to avoid $O(n^2)$ behavior.

Heap Sort and Memory Use

Heap sort uses a binary heap, usually stored in an array. For ascending order, it builds a max-heap whose root is the largest value. It then moves the root to the end of the unsorted region and restores the heap property.

With zero-based indexing, the children of node $i$ are at indices $2i+1$ and $2i+2$, and the parent of a nonroot node $i$ is at index $\left\lfloor\frac{i-1}{2}\right\rfloor$.

Heap sort has two phases:

1. Build the heap. Bottom-up construction takes $O(n)$ time.

2. Extract the maximum repeatedly. Each extraction takes $O(\log n)$ time, and the repeated extractions give a total of $O(n\log n)$ time.

The best-, average-, and worst-case running times are all $O(n\log n)$. The standard iterative implementation uses $O(1)$ extra space, is in-place, and is not stable. Its predictable worst-case bound and small memory requirement are valuable, although it is often slower in practice than quicksort because of less favorable memory-access patterns and larger constant factors.

Takeaway: Heap sort provides both a worst-case $O(n\log n)$ guarantee and constant auxiliary space, but it sacrifices stability and often typical speed.

Comparing Algorithms and Choosing One

No single algorithm is best for every input. Choose according to input size, existing order, stability needs, memory limits, and the importance of worst-case guarantees.

The standard characteristics can be summarized as follows:

• Selection sort: Best, average, and worst-case time $O(n^2)$; extra space $O(1)$; not stable; in-place.

• Insertion sort: Best-case time $O(n)$, average- and worst-case time $O(n^2)$; extra space $O(1)$; stable; in-place.

• Bubble sort: With early exit, best-case time $O(n)$, average- and worst-case time $O(n^2)$; extra space $O(1)$; stable; in-place.

• Merge sort: Best-, average-, and worst-case time $O(n\log n)$; usually $O(n)$ extra space for arrays; stable; usually not in-place.

• Quicksort: Best- and average-case time $O(n\log n)$, worst-case time $O(n^2)$; expected recursion-stack space $O(\log n)$, potentially $O(n)$; usually in-place; not stable in its standard form.

• Heap sort: Best-, average-, and worst-case time $O(n\log n)$; extra space $O(1)$; not stable; in-place.

Practical choices

• Choose insertion sort for small or nearly sorted collections.

• Choose merge sort when stable ordering and predictable $O(n\log n)$ performance matter, or when sorting linked lists or external data.

• Choose quicksort for fast general-purpose in-memory sorting when average-case performance is the main concern and pivot selection is handled well.

• Choose heap sort when worst-case $O(n\log n)$ time and constant auxiliary space are more important than typical speed.

• Choose selection sort when minimizing writes is useful and the input is small.

• Use bubble sort mainly for instructional purposes or very simple situations; it is usually dominated by insertion sort.

Final takeaway: Match the algorithm to the constraints. Nearly sorted data favors insertion sort, stable and predictable processing favors merge sort, typical in-memory speed often favors quicksort, strict worst-case and memory guarantees favor heap sort, and low write counts can favor selection sort.

• In-place operation