12. Sorting Algorithms

12. Sorting Algorithms

Sorting is a fundamental operation in computer science that arranges elements of a collection in a specific order—typically ascending or descending. Efficient sorting enables faster searching, data analysis, and optimized resource utilization. This chapter covers the most widely taught sorting algorithms, ranging from simple quadratic methods to advanced divide‑and‑conquer and linear‑time techniques, and concludes with real‑world applications.

Summary Table of Algorithms

12.1 Bubble Sort

Bubble Sort repeatedly steps through the list, compares adjacent elements, and swaps them if they are in the wrong order. The pass continues until no swaps are needed, indicating the list is sorted.

Pseudocode

for i = 0 to n‑2: swapped = false for j = 0 to n‑i‑2: if A[j] > A[j+1]: swap(A[j], A[j+1]) swapped = true if not swapped: break

Complexity Analysis

• Time: Best case O(n) when the array is already sorted (due to early exit). Average and worst case O(n²).
• Space: O(1) auxiliary.

Stability

Bubble Sort is stable because equal elements are never swapped.

Example

Sorting [5,1,4,2,8]:

1. Pass 1: [1,4,2,5,8] (swaps: 5↔1, 4↔2)
2. Pass 2: [1,2,4,5,8] (swap: 4↔2)
3. Pass 3: no swaps → algorithm terminates.

12.2 Selection Sort

Selection Sort divides the array into a sorted prefix and an unsorted suffix. Each iteration selects the smallest element from the unsorted part and swaps it with the first unsorted element.

Pseudocode

for i = 0 to n‑2: minIdx = i for j = i+1 to n‑1: if A[j] < A[minIdx]: minIdx = j swap(A[i], A[minIdx])

Complexity Analysis

• Time: O(n²) for all cases (the inner loop always scans the remaining unsorted portion).
• Space: O(1).

Stability

Selection Sort is not stable; swapping can change the relative order of equal elements.

Example

Sorting [6,4,2,5,3]:

1. i=0 → min=2 → swap → [2,4,6,5,3]
2. i=1 → min=3 → swap → [2,3,6,5,4]
3. i=2 → min=4 → swap → [2,3,4,5,6]
4. i=3 → min=3 → no change.

12.3 Insertion Sort

Insertion Sort builds the sorted array one element at a time by inserting each new element into its proper position among the already‑sorted elements.

Pseudocode

for i = 1 to n‑1: key = A[i] j = i‑1 while j ≥ 0 and A[j] > key: A[j+1] = A[j] j = j‑1 A[j+1] = key

Complexity Analysis

• Time: Best case O(n) (already sorted). Average and worst case O(n²).
• Space: O(1).

Stability

Insertion Sort is stable; equal elements retain their original order because we only shift larger elements.

Adaptive Nature

The algorithm performs exceptionally well on small or nearly sorted datasets, making it a useful subroutine in hybrid sorts (e.g., TimSort).

Example

Sorting [3,5,1,4,2]:

1. i=1, key=5 → no shift → [3,5,1,4,2]
2. i=2, key=1 → shift 5,3 → [1,3,5,4,2]
3. i=3, key=4 → shift 5 → [1,3,4,5,2]
4. i=4, key=2 → shift 5,4,3 → [1,2,3,4,5]

12.4 Merge Sort

Merge Sort follows the divide‑and‑conquer paradigm: recursively split the array into halves, sort each half, and then merge the two sorted halves.

Pseudocode

mergeSort(A, l, r): if l < r: m = (l + r) // 2 mergeSort(A, l, m) mergeSort(A, m+1, r) merge(A, l, m, r) merge(A, l, m, r): L = A[l..m] R = A[m+1..r] i = j = 0 k = l while i < len(L) and j < len(R): if L[i] ≤ R[j]: A[k] = L[i]; i += 1 else: A[k] = R[j]; j += 1 k += 1 copy remaining elements of L (if any) to A[k..r] copy remaining elements of R (if any) to A[k..r]

Complexity Analysis

• Time: O(n log n) in all cases.
• Space: O(n) auxiliary for the temporary subarrays during merging.

Stability

Merge Sort is stable because the merge step prefers the left element when values are equal (≤).

Example

Sorting [38,27,43,3,9,82,10]:

• Split → [38,27,43,3] and [9,82,10]
• Further split until singletons.
• Merge step yields sorted array [3,9,10,27,38,43,82].

12.5 Quick Sort

Quick Sort selects a pivot element, partitions the array so that elements less than the pivot go left and greater go right, then recursively sorts the partitions.

Pseudocode

quickSort(A, l, r): if l < r: p = partition(A, l, r) quickSort(A, l, p‑1) quickSort(A, p+1, r) partition(A, l, r): pivot = A[r] i = l‑1 for j = l to r‑1: if A[j] ≤ pivot: i += 1 swap(A[i], A[j]) swap(A[i+1], A[r]) return i+1

Complexity Analysis

• Time: Average case O(n log n). Best case O(n log n) with good pivot splits. Worst case O(n²) when the pivot is consistently the smallest or largest element (e.g., already sorted array with naïve pivot). Using a random pivot yields expected O(n log n).
• Space: O(log n) stack space due to recursion depth (in‑place partitioning).

Stability

Quick Sort is not stable; the partitioning step can reorder equal elements.

Example

Sorting [10,80,30,90,40,50,70] with pivot = last element (70):

1. Partition → [10,30,40,50,70,90,80] (pivot index 4).
2. Recursively sort left part [10,30,40,50] and right part [90,80].
3. Final sorted array: [10,30,40,50,70,80,90].

12.6 Heap Sort

Heap Sort builds a max‑heap from the input data, then repeatedly extracts the maximum element and places it at the end of the array, reducing the heap size each time.

Key Points

• Time: O(n log n) for all cases.
• Space: O(1) auxiliary (in‑place).
• Stability: Not stable.

Brief Pseudocode

heapSort(A): buildMaxHeap(A) for i = n‑1 downto 1: swap(A[0], A[i]) // move max to end heapSize = heapSize‑1 maxHeapify(A, 0) // restore heap property on reduced heap

12.7 Counting Sort

Counting Sort is a non‑comparison algorithm suitable for integers within a known range [0, k]. It works by counting occurrences of each value, then computing prefix sums to determine positions.

Pseudocode

for x in A: count[x] += 1 for i = 1 to k: count[i] += count[i‑1] // prefix sum output = array of size n for x in reversed(A): // iterate reversed to maintain stability output[count[x]‑1] = x count[x] -= 1

Complexity Analysis

• Time: O(n + k).
• Space: O(k) for the count array plus O(n) for output.

Stability

Counting Sort is stable because we place elements from the end of the input array, preserving original order among equal keys.

Example

Sorting [4,2,2,8,3,3,1] with k = 8:

• Count array after first pass: [0,1,2,2,1,0,0,0,1]
• Prefix sums: [0,1,3,5,6,6,6,6,7]
• Iterating reversed input yields output [1,2,2,3,3,4,8].

12.8 Radix Sort

Radix Sort processes integers digit by digit, using a stable subroutine (commonly Counting Sort) for each digit position, starting from the least significant digit (LSD) to the most significant digit (MSD).

Pseudocode

radixSort(A, b): // b = base (e.g., 10) maxVal = max(A) d = ceil(log_b(maxVal+1)) // number of digits for digit = 0 to d‑1: // key = (A[i] // b^digit) % b stableSort(A, key = (A[i] // b^digit) % b)

Complexity Analysis

• Time: O(d·(n + b)) = O(n log_b(max)). For a fixed base (e.g., 10) this is O(n log n) in the worst case, but linear for bounded integer size.
• Space: O(n + b) for the auxiliary buckets used by the stable subroutine.

Stability

Radix Sort is stable as long as the digit‑wise subroutine is stable (Counting Sort fulfills this).

Example (Base 10)

Sorting [170,45,75,90,802,24,2,66]:

• Pass 1 (units): [170,90,802,2,24,45,75,66]
• Pass 2 (tens): [802,2,24,45,66,170,75,90]
• Pass 3 (hundreds):[2,24,45,66,75,90,170,802]

12.9 Real‑Life Sorting Applications

Sorting is ubiquitous in software systems. Below are common scenarios where the algorithms discussed are employed:

• Database query results: ORDER BY clauses often use external merge sort when data exceeds memory.
• File systems: Directory listings are sorted alphabetically for user‑friendly navigation.
• E‑commerce: Products are sorted by price, rating, relevance, or popularity to improve shopping experience.
• Leaderboards: Game scores or contest results are sorted descending to display top performers.
• Graphics rendering: Painter’s algorithm sorts polygons by depth (z‑value) to render distant objects first.
• Log processing: Timestamps are sorted to enable chronological analysis and debugging.

Choosing the appropriate sorting algorithm depends on data size, key distribution, memory constraints, and whether stability is required. For small or nearly sorted data, Insertion Sort excels; for guaranteed O(n log n) worst‑case performance, Merge Sort or Heap Sort are preferred; when average‑case speed matters and extra space is limited, Quick Sort is often chosen; and for integer keys with a limited range, Counting Sort or Radix Sort provide linear‑time solutions.