9 Sorting Algorithms

Foundations of comparison sorting

Sorting rearranges items according to a specified ordering, such as ascending numerical order or alphabetical order. Once data is ordered, binary search becomes possible, duplicate values are easier to detect, and reports can be produced in a predictable sequence.

The algorithms in this guide are comparison-based: they determine order by comparing pairs of elements. For arbitrary input, comparison-based sorting cannot guarantee a worst-case running time better than $\Omega(n \log n)$. Simpler quadratic algorithms remain useful because they are easy to implement, effective on small inputs, or efficient when the data is already nearly ordered.

Two questions organize the analysis of every sorting algorithm:

• How does its running time grow with input size $n$?

• What extra memory does it need, and does it preserve the order of equal keys?

A useful first distinction is between quadratic growth, $O(n^2)$, and the usual efficient comparison-sorting target, $O(n \log n)$. Some algorithms can achieve $O(n)$ on especially favorable inputs, but that does not make their general performance linear.

Takeaway: Sorting is not only about producing the right order; algorithm choice depends on growth rate, memory, input order, and treatment of equal keys.

How to evaluate a sorting algorithm

Three properties are particularly important when comparing sorting methods.

Time complexity should be reported for the best case, average case, and worst case. For example, an algorithm may run in $O(n)$ on an already sorted array but still require $O(n^2)$ time on a difficult input.

In-place sorting means that the algorithm uses only a small amount of additional memory beyond the input array. This description does not necessarily include the recursion stack, which should be reported separately when it matters.

Stability means that records with equal keys retain their original relative order. For example, if the input contains $(\text{Adams},1)$ before $(\text{Adams},2)$, a stable sort keeps the first record before the second after sorting by last name. Stability supports multi-key workflows, such as sorting employees by department and then by salary.

A compact comparison of the main algorithms is:

• Bubble sort: stable and in-place; best case $O(n)$ with early termination, but average and worst cases $O(n^2)$.

• Selection sort: in-place and usually not stable; $O(n^2)$ in every listed time case.

• Insertion sort: stable and in-place; best case $O(n)$, average and worst cases $O(n^2)$.

• Merge sort: stable with the usual merge rule; $O(n \log n)$ in every listed time case, but typically needs $O(n)$ extra array space.

• Quicksort: usually in-place and typically not stable; average case $O(n \log n)$, but worst case $O(n^2)$.

Takeaway: No single complexity label is sufficient. Always connect time bounds with space requirements, stability, and the assumptions behind the best or average case.

Bubble sort: adjacent exchanges

Bubble sort repeatedly compares adjacent elements. When the left element is greater than the right element, the algorithm swaps them. After one complete pass, the largest element in the remaining unsorted portion has moved to the end of that portion.

For the list $[5,1,4,2]$, the first comparisons produce:

1. Compare $5$ and $1$, then swap: $[1,5,4,2]$.

2. Compare $5$ and $4$, then swap: $[1,4,5,2]$.

3. Compare $5$ and $2$, then swap: $[1,4,2,5]$.

The next pass can ignore the final position because it is already correct. An early-exit flag stops the algorithm when a full pass makes no swaps. Consequently, the best case is $O(n)$ when the input is already sorted, while the average and worst cases are $O(n^2)$. Bubble sort uses $O(1)$ extra space and is stable when it swaps only strictly out-of-order adjacent elements.

Takeaway: Bubble sort is useful for illustrating adjacent exchanges and early termination, but it is rarely suitable for large inputs.

Selection sort: choosing the next minimum

Selection sort maintains a sorted prefix and an unsorted remainder. On each pass, it scans the remainder to find its smallest element, then swaps that element with the first unsorted position.

For $[4,2,7,1]$, the first pass finds $1$ and produces $[1,2,7,4]$. The next smallest value is $2$, which is already in place. The final remaining adjustment produces $[1,2,4,7]$.

Selection sort always scans the unsorted portion, even when the array is already sorted. Therefore, its best, average, and worst-case running times are all $O(n^2)$. It uses $O(1)$ extra space and performs only about $n$ swaps, which can be valuable when writes are expensive. The standard implementation is not stable because a long-distance swap can change the relative order of equal keys.

Takeaway: Choose selection sort when minimizing swaps matters more than minimizing comparisons, not when the input is large or nearly sorted.

Insertion sort: exploiting existing order

Insertion sort grows a sorted prefix one item at a time. It stores the next value, shifts every larger prefix element one position to the right, and inserts the stored value into the gap.

For $[4,2,5,1]$:

1. Insert $2$ before $4$, giving $[2,4,5,1]$.

2. Insert $5$; it is already in the correct position.

3. Shift $5$, $4$, and $2$, then insert $1$, giving $[1,2,4,5]$.

On an already sorted or nearly sorted array, few shifts are needed, so the best case is $O(n)$. The average and worst cases are $O(n^2)$, with reverse-sorted input providing a difficult case. Insertion sort uses $O(1)$ extra space and is stable when equal elements are not moved past one another.

An inversion measures a pair that is in the wrong relative order. Insertion sort performs shifts closely related to the number of inversions, which explains why it performs well when the input has only a few such pairs.

Takeaway: Insertion sort is a strong simple choice for small arrays, nearly sorted data, and small subarrays inside more complex sorting strategies.

Merge sort: divide, solve, and merge

Merge sort applies divide and conquer. It divides the array into two halves, recursively sorts each half, and merges the two sorted results. The merge step repeatedly chooses the smaller first remaining element from the two halves.

For $[8,3,6,2]$, the process can be summarized as:

• Divide into $[8,3]$ and $[6,2]$.

• Divide again into single-element arrays: $[8]$, $[3]$, $[6]$, and $[2]$.

• Merge to obtain $[3,8]$ and $[2,6]$.

• Merge those results to obtain $[2,3,6,8]$.

Each recursion level processes all $n$ elements during merging, and there are approximately $\log n$ levels. Thus the best, average, and worst-case running times are all $O(n \log n)$. The usual array implementation uses $O(n)$ auxiliary space. It is stable when the merge chooses the element from the left subarray first whenever the two compared keys are equal.

Takeaway: Merge sort trades additional memory for predictable $O(n \log n)$ performance and stable ordering.

Quicksort: partitioning around a pivot

Quicksort also uses divide and conquer, but it divides the array through partitioning rather than by fixed halves. It chooses a pivot, rearranges the elements so that smaller values lie on one side and larger values lie on the other, and then recursively sorts the two resulting partitions.

For $[7,2,9,4,3]$, choosing $4$ as the pivot can produce $[2,3,4,9,7]$ after partitioning. The pivot $4$ is in its final position, while the subarrays $[2,3]$ and $[9,7]$ still require sorting.

When partitions are reasonably balanced, quicksort runs in $O(n \log n)$. Repeatedly unbalanced partitions can produce $O(n^2)$ worst-case time, especially with a poor pivot strategy on already sorted or specially arranged input. In-place partitioning generally uses $O(1)$ extra array space, but the recursion stack requires $O(\log n)$ space on average and can require $O(n)$ in the worst case. Standard implementations are not stable.

Random shuffling, randomized pivots, median-of-three selection, and switching to insertion sort for tiny subarrays are common ways to improve practical behavior.

Takeaway: Quicksort can be fast and memory-efficient, but its performance depends strongly on controlling partition balance.

Choosing the right algorithm

Algorithm selection should reflect the input and the required guarantees rather than relying on one universal ranking.

• Choose insertion sort for small arrays or data that is already nearly sorted.

• Choose selection sort when the number of writes or swaps must be kept low and quadratic comparisons are acceptable.

• Choose merge sort when stable ordering and a guaranteed $O(n \log n)$ bound are important, and additional memory is available.

• Choose quicksort when average-case speed and low extra array memory are priorities, provided pivot selection or randomization controls worst-case risk.

• Treat bubble sort primarily as a teaching tool or as a solution for very small, simple inputs.

For production software, a trusted library sort is usually preferable to a new hand-written implementation. Library algorithms can combine strategies, use carefully engineered partitioning, and exploit existing order. Stability and memory behavior should still be checked because different libraries make different guarantees.

A practical decision process is:

1. Ask whether stable ordering is required.

2. Estimate the input size and how ordered the data already is.

3. Check whether additional memory is available.

4. Decide whether worst-case guarantees or average-case speed matter more.

5. Prefer a reliable library implementation when one satisfies the requirements.

Takeaway: The best sorting algorithm depends on input size, existing order, memory limits, stability requirements, write costs, and acceptable worst-case behavior.

Key conclusions

The main ideas can be connected as follows:

• Sorting makes later operations easier by imposing an order.

• Comparison-based sorting has a general worst-case lower bound of $\Omega(n \log n)$.

• Bubble sort and insertion sort can achieve $O(n)$ best cases, but both have quadratic average and worst cases.

• Selection sort is quadratic in every listed time case, but it uses constant extra space and relatively few swaps.

• Merge sort guarantees $O(n \log n)$ time and can be stable, at the cost of typically requiring $O(n)$ auxiliary memory.

• Quicksort often performs well with balanced partitions and low array overhead, but poor pivot choices can cause $O(n^2)$ time and a large recursion stack.

• Stability, in-place behavior, and complexity describe different properties; an algorithm can be strong in one and weak in another.

When comparing algorithms, state the assumptions behind each claim. For example, bubble sort's linear best case depends on early termination, and quicksort's average-case bound depends on suitable pivot behavior or randomization.