Quadratic Sorting Algorithms theory

The three elementary sorting algorithms exhibit distinct analytical comparison profiles governed by their inner loop termination invariants:



1. Selection Sort:

- Comparison Mechanism: In pass i (from 0 to n − 2), the algorithm scans the remaining unsorted suffix A[i .. n-1] to locate the minimum key. The inner loop always executes exactly n − 1 − i comparisons, independent of the values in the array.

- Total Comparisons: C(n) = ∑_{i=0}^{n-2} (n − 1 − i) = (n − 1) + (n − 2) + ... + 1 = n(n − 1)/2.

- Best, Worst, and Average Cases: All identically Θ(n²). Selection Sort is completely non-adaptive with respect to comparisons.



2. Bubble Sort:

- Comparison Mechanism: Compares adjacent pairs A[j] and A[j+1] for j from 0 to n − 2 − i.

- Worst-Case (Reverse-Sorted): Without early exit or on reversed keys, executes ∑_{i=0}^{n-2} (n − 1 − i) = n(n − 1)/2 comparisons = Θ(n²).

- Best-Case (Already Sorted with Early-Exit Flag): If a boolean swapped flag tracks whether any exchange occurred in a pass, the first pass verifies sortedness with n − 1 comparisons and immediately terminates: C_best(n) = n − 1 = Θ(n).

- Average-Case: Θ(n²) comparisons.



3. Insertion Sort:

- Comparison Mechanism: Inserts A[i] into the sorted prefix A[0 .. i-1] by shifting larger elements right. In pass i, it performs between 1 and i comparisons.

- Best-Case (Already Sorted): Exactly 1 comparison per element: C_best(n) = n − 1 = Θ(n).

- Worst-Case (Reverse-Sorted): Requires i comparisons per element: C_worst(n) = ∑_{i=1}^{n-1} i = n(n − 1)/2 = Θ(n²).

- Average-Case (Random Permutation): Each element is expected to move halfway through the sorted prefix: E[C_i] ≈ i/2, yielding C_avg(n) = ∑_{i=1}^{n-1} i/2 = n(n − 1)/4 = Θ(n²).

Let A = (a₁, a₂, ..., a_n) be a permutation of n distinct keys. An inversion is defined as a pair of indices (i, j) such that i < j and a_i > a_j.



1. Maximum and Expected Inversions:

- An array is sorted if and only if it contains 0 inversions.

- A reverse-sorted array contains the maximum possible number of inversions: I_max = (n choose 2) = n(n − 1) / 2.

- Consider any permutation π and its reverse π^R. For every pair (i, j) with i < j, exactly one of π or π^R contains an inversion for that pair. Since there are (n choose 2) pairs, the sum of inversions in π and π^R is exactly n(n − 1)/2.

- By symmetry across all n! equally likely permutations, the expected number of inversions in a uniform random permutation is exactly:

E[I] = (1/2) · n(n − 1)/2 = n(n − 1) / 4.



2. Effect of an Adjacent Swap:

- Swapping two adjacent elements a_k and a_{k+1} changes the relative order of only that single pair (k, k+1). The relative order of all other pairs (i, j) remains completely unchanged.

- Therefore, a single adjacent swap can decrease the total number of inversions by at most 1.



3. Conclusion:

- To sort an array, an algorithm that swaps only adjacent elements must eliminate all inversions.

- Thus, the number of swaps S performed by any adjacent-swap sorting algorithm satisfies S >= I(A).

- On average, the number of swaps is at least E[S] >= E[I] = n(n − 1)/4 = Ω(n²).

- Because each swap requires at least one preceding comparison, the average number of comparisons must also be Ω(n²).

A sorting algorithm is defined as stable if elements with equal comparison keys appear in the output array in the exact same relative order as they were presented in the input array. Formally, if A[i] == A[j] and i < j in the input, then in the sorted output, the element originally at index i must precede the element originally at index j.



Stability is crucial in real-world software engineering when sorting records with multiple secondary attributes (for example, sorting a list of transactions first by transaction time, and subsequently sorting by customer name; a stable sort preserves the chronological ordering within each customer group).



1. Bubble Sort: STABLE (when correctly implemented).

- Adjacent elements are swapped only when A[j] > A[j+1]. If A[j] == A[j+1], the algorithm skips the swap (`>` rather than `>=`), strictly preserving their relative input order.



2. Insertion Sort: STABLE (when correctly implemented).

- When inserting key A[i] into the sorted prefix, elements are shifted right only while A[j] > key. The search for the insertion slot halts as soon as an element equal to key is encountered (A[j] <= key), placing the new element to the right of any identical keys, preserving relative order.



3. Selection Sort: UNSTABLE.

- Selection Sort locates the minimum key in the unsorted suffix and swaps it with A[i]. This long-range swap can jump over identical elements. For example, consider the array [4a, 4b, 2]. In the first pass, 2 is swapped with 4a, yielding [2, 4b, 4a]. The equal keys 4a and 4b have had their relative order reversed, violating stability.

In physical computer hardware, writing to memory is significantly more expensive than reading from memory. In solid-state storage (Flash memory, EEPROM, Phase Change Memory, and NVMe SSDs), write operations cause physical oxide degradation, consume substantial write-buffer power, and require erase-block cycles.



Comparing the memory write profiles of quadratic algorithms:

1. Bubble Sort:

- Executes up to n(n − 1)/2 swaps in the worst case, and n(n − 1)/4 swaps on average.

- Each swap involves 3 memory move operations (or 2 memory writes and 1 read). For n = 1,000, Bubble Sort can execute ~250,000 to 500,000 writes, creating severe write amplification.



2. Insertion Sort:

- Executes up to n(n − 1)/2 element shifts in the worst case, and n(n − 1)/4 shifts on average.



3. Selection Sort:

- In each outer pass i (from 0 to n − 2), Selection Sort performs comparisons strictly in CPU registers without modifying memory. Exactly ONE swap is executed at the conclusion of each pass to place the minimum element in position.

- Total swaps: At most n − 1 swaps in the worst case (and 0 swaps if each element is already in place).

- Total memory writes: At most 2(n − 1) writes.

- For n = 1,000, Selection Sort executes at most 999 swaps (~1,998 writes), which is over 250 times fewer writes than Bubble Sort!

- Therefore, in embedded microcontrollers with limited EEPROM write cycles (e.g., 100,000 write endurance limits) or battery-constrained sensor nodes, Selection Sort is dramatically superior despite having the same O(n²) comparison complexity.

Although Merge Sort has a superior asymptotic time complexity of O(n log n) compared to Insertion Sort's O(n²), Insertion Sort consistently executes faster in real wall-clock time on modern microprocessors for small arrays (typically n between 16 and 32 elements). This empirical phenomenon is governed by three architectural factors:



1. Cache Locality (Spatial and Temporal):

- Insertion Sort operates completely in-place within a contiguous memory block that fits comfortably within the processor's high-speed L1 data cache (typically 32 KB). All reads and writes hit L1 cache with ~1 ns latency.

- Merge Sort requires an auxiliary buffer of size O(n) and repeatedly copies elements back and forth between the input array and auxiliary memory, generating twice as many memory writes and thrashing cache lines.



2. Algorithmic Constant Factor & Instruction Overhead:

- Insertion Sort's inner loop consists of a simple comparison, a register shift, and a pointer decrement—often compiling into just 3 to 4 assembly instructions.

- Merge Sort incurs the heavy overhead of recursive function calls, stack frame allocation, midpoint division, and merge buffer pointer reconciliation.



3. Hybrid Algorithms (Timsort & Introsort):

- Modern high-performance production libraries (Python's built-in `sort`, Java's `Arrays.sort`, C++ `std::sort`) exploit this principle by implementing hybrid algorithms: they divide large datasets using Merge Sort or Quicksort, but switch immediately to Insertion Sort as soon as recursive subarrays reach a threshold size of n <= 16 to 32 elements.

In combinatorial mathematics, the structure of an unsorted permutation can be characterized by different metric distances from the identity permutation (1, 2, ..., n):



1. Kendall-tau Distance (Inversion Distance):

- Counts the minimum number of adjacent transpositions (swaps of neighboring elements (i, i+1)) required to transform permutation π into the identity permutation.

- It equals the number of inversions: d_K(π, id) = I(π) = |{(i, j) : i < j and π(i) > π(j)}|.

- Range: 0 <= d_K <= n(n − 1)/2.

- This distance directly dictates the exact swap count of Bubble Sort and the shift count of Insertion Sort.



2. Cayley's Transposition Distance:

- Counts the minimum number of arbitrary transpositions (swapping any two elements (i, j), regardless of distance) required to transform π into the identity permutation.

- By permutation group theory, any permutation can be decomposed into a disjoint set of c(π) cyclic orbits (cycles).

- Cayley proved that the minimum number of arbitrary transpositions required is exactly: d_C(π, id) = n − c(π).

- Range: 0 <= d_C <= n − 1.

- This distance corresponds directly to the theoretical minimum number of swaps achievable by algorithms that can swap across arbitrary distances (such as Selection Sort and Cycle Sort). Specifically, Cycle Sort achieves the absolute theoretical minimum memory write bound: each element is written to memory at most once if it is part of a non-trivial cycle, or zero times if already correctly positioned, yielding strictly optimal write efficiency for write-sensitive storage.

Standard naive Bubble Sort unconditionally executes n − 1 outer passes regardless of the array's state. However, by introducing a boolean state variable `swapped`, Bubble Sort can detect when an array has become sorted before completing all passes.



Algorithm Structure:

```

for i = 0 to n - 2:

swapped = false

for j = 0 to n - 2 - i:

if A[j] > A[j+1]:

swap(A[j], A[j+1])

swapped = true

if not swapped:

break // Array is fully sorted; terminate immediately

```



Analytical Behavior:

1. If the input array is already sorted: In the very first pass (i = 0), the algorithm performs n − 1 comparisons. Because A[j] <= A[j+1] for all j, no swaps occur. The condition `not swapped` triggers an immediate break. Total comparisons: n − 1. Runtime: Θ(n).

2. If the array has only a few out-of-order elements near their final positions: The algorithm terminates after k passes (where k is the maximum distance an element must bubble), executing O(k · n) operations.

3. The Turtle and Hare Problem: A major asymmetry in unidirectional Bubble Sort is that large elements near the start ('hares') advance rapidly toward the end in a single pass, whereas small elements near the end ('turtles') move leftward by only one position per pass. For instance, if the minimum element is positioned at the final index A[n-1], it requires n − 1 complete passes to drift to index 0, requiring Θ(n²) operations even if the rest of the array is sorted.

4. Bidirectional Mitigation (Cocktail Shaker Sort): Bidirectional Bubble Sort alternates scanning directions: left-to-right (bubbling the maximum rightward) followed by right-to-left (bubbling the minimum leftward). This bidirectional traversal eliminates the turtle bottleneck, accelerating convergence on partially sorted inputs while preserving simplicity and in-place stability.