Sorting Algorithms
Linear & Non-Linear — Pseudocode, Worked Examples (Array Size = 10) & Time–Space Complexity
Analysis
Rajnish Pandey | [Link] Information Technology, Semester V | Assignment Unit-1
This document covers both categories of sorting algorithms. Part 1 covers Non-Linear (comparison-
based) Sorting — Bubble, Selection, Insertion, Shell, Merge, Quick and Heap Sort. Part 2 covers Linear
(non-comparison-based) Sorting — Counting, Radix and Bucket Sort. Every worked example in both
parts uses an array of size 10, with pseudocode, step-by-step traces, and time & space complexity
analysis for each algorithm.
PART 1 — NON-LINEAR SORTING ALGORITHMS
(a) Bubble Sort
Bubble Sort repeatedly steps through the array, compares adjacent elements, and swaps them if they
are in the wrong order. Larger elements 'bubble up' to the end of the array with each pass. An optional
flag stops early if no swaps occur in a pass.
Pseudocode
BUBBLE_SORT(A, n)
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 swapped == false
break // array already sorted
return A
Worked Examples
Example 1: Input = [15, 3, 18, 7, 1, 12, 9, 20, 5, 11]
Pass 1: [3, 15, 7, 1, 12, 9, 18, 5, 11, 20]
Pass 2: [3, 7, 1, 12, 9, 15, 5, 11, 18, 20]
Pass 3: [3, 1, 7, 9, 12, 5, 11, 15, 18, 20]
Pass 4: [1, 3, 7, 9, 5, 11, 12, 15, 18, 20]
Pass 5: [1, 3, 7, 5, 9, 11, 12, 15, 18, 20]
Pass 6: [1, 3, 5, 7, 9, 11, 12, 15, 18, 20]
Pass 7 (no swaps → stop): [1, 3, 5, 7, 9, 11, 12, 15, 18, 20]
Example 2: Input = [8, 19, 2, 14, 6, 17, 10, 1, 13, 4]
Pass 1: [8, 2, 14, 6, 17, 10, 1, 13, 4, 19]
Pass 2: [2, 8, 6, 14, 10, 1, 13, 4, 17, 19]
Pass 3: [2, 6, 8, 10, 1, 13, 4, 14, 17, 19]
Pass 4: [2, 6, 8, 1, 10, 4, 13, 14, 17, 19]
Pass 5: [2, 6, 1, 8, 4, 10, 13, 14, 17, 19]
Pass 6: [2, 1, 6, 4, 8, 10, 13, 14, 17, 19]
Pass 7: [1, 2, 4, 6, 8, 10, 13, 14, 17, 19]
Pass 8 (no swaps → stop): [1, 2, 4, 6, 8, 10, 13, 14, 17, 19]
Example 3: Input = [20, 5, 16, 9, 2, 13, 7, 18, 3, 11]
Pass 1: [5, 16, 9, 2, 13, 7, 18, 3, 11, 20]
Pass 2: [5, 9, 2, 13, 7, 16, 3, 11, 18, 20]
Pass 3: [5, 2, 9, 7, 13, 3, 11, 16, 18, 20]
Pass 4: [2, 5, 7, 9, 3, 11, 13, 16, 18, 20]
Pass 5: [2, 5, 7, 3, 9, 11, 13, 16, 18, 20]
Pass 6: [2, 5, 3, 7, 9, 11, 13, 16, 18, 20]
Pass 7: [2, 3, 5, 7, 9, 11, 13, 16, 18, 20]
Pass 8 (no swaps → stop): [2, 3, 5, 7, 9, 11, 13, 16, 18, 20]
Time & Space Complexity
Best Case Average Case Worst Case Space Complexity
O(n) O(n²) O(n²) O(1)
Best case O(n) occurs when the array is already sorted — the swapped flag lets the algorithm exit after a single
pass. Average/worst case O(n²) occurs on random/reverse-sorted input, requiring ≈n(n-1)/2 comparisons and
swaps. Sorts in place (O(1) space); stable.
(b) Selection Sort
Selection Sort divides the array into a sorted and an unsorted part. Each pass scans the unsorted part for
the minimum element and swaps it into place.
Pseudocode
SELECTION_SORT(A, n)
for i = 0 to n-2
min_idx = i
for j = i+1 to n-1
if A[j] < A[min_idx]
min_idx = j
swap(A[i], A[min_idx])
return A
Worked Examples
Example 1: Input = [35, 23, 38, 27, 21, 32, 29, 40, 25, 31]
After i=0 (min=21): [21, 23, 38, 27, 35, 32, 29, 40, 25, 31]
After i=1 (min=23): [21, 23, 38, 27, 35, 32, 29, 40, 25, 31]
After i=2 (min=25): [21, 23, 25, 27, 35, 32, 29, 40, 38, 31]
After i=3 (min=27): [21, 23, 25, 27, 35, 32, 29, 40, 38, 31]
After i=4 (min=29): [21, 23, 25, 27, 29, 32, 35, 40, 38, 31]
After i=5 (min=31): [21, 23, 25, 27, 29, 31, 35, 40, 38, 32]
After i=6 (min=32): [21, 23, 25, 27, 29, 31, 32, 40, 38, 35]
After i=7 (min=35): [21, 23, 25, 27, 29, 31, 32, 35, 38, 40]
After i=8 (min=38): [21, 23, 25, 27, 29, 31, 32, 35, 38, 40]
Example 2: Input = [28, 39, 22, 34, 26, 37, 30, 21, 33, 24]
After i=0 (min=21): [21, 39, 22, 34, 26, 37, 30, 28, 33, 24]
After i=1 (min=22): [21, 22, 39, 34, 26, 37, 30, 28, 33, 24]
After i=2 (min=24): [21, 22, 24, 34, 26, 37, 30, 28, 33, 39]
After i=3 (min=26): [21, 22, 24, 26, 34, 37, 30, 28, 33, 39]
After i=4 (min=28): [21, 22, 24, 26, 28, 37, 30, 34, 33, 39]
After i=5 (min=30): [21, 22, 24, 26, 28, 30, 37, 34, 33, 39]
After i=6 (min=33): [21, 22, 24, 26, 28, 30, 33, 34, 37, 39]
After i=7 (min=34): [21, 22, 24, 26, 28, 30, 33, 34, 37, 39]
After i=8 (min=37): [21, 22, 24, 26, 28, 30, 33, 34, 37, 39]
Example 3: Input = [40, 25, 36, 29, 22, 33, 27, 38, 23, 31]
After i=0 (min=22): [22, 25, 36, 29, 40, 33, 27, 38, 23, 31]
After i=1 (min=23): [22, 23, 36, 29, 40, 33, 27, 38, 25, 31]
After i=2 (min=25): [22, 23, 25, 29, 40, 33, 27, 38, 36, 31]
After i=3 (min=27): [22, 23, 25, 27, 40, 33, 29, 38, 36, 31]
After i=4 (min=29): [22, 23, 25, 27, 29, 33, 40, 38, 36, 31]
After i=5 (min=31): [22, 23, 25, 27, 29, 31, 40, 38, 36, 33]
After i=6 (min=33): [22, 23, 25, 27, 29, 31, 33, 38, 36, 40]
After i=7 (min=36): [22, 23, 25, 27, 29, 31, 33, 36, 38, 40]
After i=8 (min=38): [22, 23, 25, 27, 29, 31, 33, 36, 38, 40]
Time & Space Complexity
Best Case Average Case Worst Case Space Complexity
O(n²) O(n²) O(n²) O(1)
Always scans the full unsorted portion regardless of arrangement, so best/average/worst are all ≈n(n-1)/2 = O(n²)
comparisons. Only n-1 swaps total, useful when writes are costly. O(1) space; not stable in basic form.
(c) Insertion Sort
Insertion Sort builds the sorted array one element at a time, inserting each new 'key' into its correct
position among the already-sorted elements to its left.
Pseudocode
INSERTION_SORT(A, n)
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
return A
Worked Examples
Example 1: Input = [55, 43, 58, 47, 41, 52, 49, 60, 45, 51]
Insert 43: [43, 55, 58, 47, 41, 52, 49, 60, 45, 51]
Insert 58: [43, 55, 58, 47, 41, 52, 49, 60, 45, 51]
Insert 47: [43, 47, 55, 58, 41, 52, 49, 60, 45, 51]
Insert 41: [41, 43, 47, 55, 58, 52, 49, 60, 45, 51]
Insert 52: [41, 43, 47, 52, 55, 58, 49, 60, 45, 51]
Insert 49: [41, 43, 47, 49, 52, 55, 58, 60, 45, 51]
Insert 60: [41, 43, 47, 49, 52, 55, 58, 60, 45, 51]
Insert 45: [41, 43, 45, 47, 49, 52, 55, 58, 60, 51]
Insert 51: [41, 43, 45, 47, 49, 51, 52, 55, 58, 60]
Example 2: Input = [48, 59, 42, 54, 46, 57, 50, 41, 53, 44]
Insert 59: [48, 59, 42, 54, 46, 57, 50, 41, 53, 44]
Insert 42: [42, 48, 59, 54, 46, 57, 50, 41, 53, 44]
Insert 54: [42, 48, 54, 59, 46, 57, 50, 41, 53, 44]
Insert 46: [42, 46, 48, 54, 59, 57, 50, 41, 53, 44]
Insert 57: [42, 46, 48, 54, 57, 59, 50, 41, 53, 44]
Insert 50: [42, 46, 48, 50, 54, 57, 59, 41, 53, 44]
Insert 41: [41, 42, 46, 48, 50, 54, 57, 59, 53, 44]
Insert 53: [41, 42, 46, 48, 50, 53, 54, 57, 59, 44]
Insert 44: [41, 42, 44, 46, 48, 50, 53, 54, 57, 59]
Example 3: Input = [60, 45, 56, 49, 42, 53, 47, 58, 43, 51]
Insert 45: [45, 60, 56, 49, 42, 53, 47, 58, 43, 51]
Insert 56: [45, 56, 60, 49, 42, 53, 47, 58, 43, 51]
Insert 49: [45, 49, 56, 60, 42, 53, 47, 58, 43, 51]
Insert 42: [42, 45, 49, 56, 60, 53, 47, 58, 43, 51]
Insert 53: [42, 45, 49, 53, 56, 60, 47, 58, 43, 51]
Insert 47: [42, 45, 47, 49, 53, 56, 60, 58, 43, 51]
Insert 58: [42, 45, 47, 49, 53, 56, 58, 60, 43, 51]
Insert 43: [42, 43, 45, 47, 49, 53, 56, 58, 60, 51]
Insert 51: [42, 43, 45, 47, 49, 51, 53, 56, 58, 60]
Time & Space Complexity
Best Case Average Case Worst Case Space Complexity
O(n) O(n²) O(n²) O(1)
Best case O(n) on already-sorted input (inner while never runs). Worst case O(n²) on reverse-sorted input (each key
shifts to the front). O(1) space; stable — good for small/nearly-sorted arrays.
(d) Shell Sort
Shell Sort generalises Insertion Sort by first sorting far-apart elements (using a gap), progressively
shrinking the gap to 1, where a final cheap insertion pass completes the sort. Gap sequence used: n/2,
n/4, ..., 1.
Pseudocode
SHELL_SORT(A, n)
gap = n / 2
while gap > 0
for i = gap to n-1
temp = A[i]
j = i
while j >= gap and A[j-gap] > temp
A[j] = A[j-gap]
j = j - gap
A[j] = temp
gap = gap / 2
return A
Worked Examples
Example 1: Input = [75, 63, 78, 67, 61, 72, 69, 80, 65, 71]
After gap = 5: [72, 63, 78, 65, 61, 75, 69, 80, 67, 71]
After gap = 2: [61, 63, 67, 65, 69, 71, 72, 75, 78, 80]
After gap = 1: [61, 63, 65, 67, 69, 71, 72, 75, 78, 80]
Example 2: Input = [68, 79, 62, 74, 66, 77, 70, 61, 73, 64]
After gap = 5: [68, 70, 61, 73, 64, 77, 79, 62, 74, 66]
After gap = 2: [61, 62, 64, 66, 68, 70, 74, 73, 79, 77]
After gap = 1: [61, 62, 64, 66, 68, 70, 73, 74, 77, 79]
Example 3: Input = [80, 65, 76, 69, 62, 73, 67, 78, 63, 71]
After gap = 5: [73, 65, 76, 63, 62, 80, 67, 78, 69, 71]
After gap = 2: [62, 63, 67, 65, 69, 71, 73, 78, 76, 80]
After gap = 1: [62, 63, 65, 67, 69, 71, 73, 76, 78, 80]
Time & Space Complexity
Best Case Average Case Worst Case Space Complexity
O(n log n) ≈O(n^1.25)–O(n^1.5)* O(n²)* O(1)
*Depends on gap sequence; with gap=n/2, worst case is O(n²); better sequences (Hibbard, Sedgewick) improve this.
Best case O(n log n) on sorted input. O(1) space; not stable.
(e) Merge Sort
Merge Sort is a divide-and-conquer algorithm: recursively splits the array into halves until single
elements remain, then merges sub-arrays back together in sorted order.
Pseudocode
MERGE_SORT(A, l, r)
if l < r
m = (l + r) / 2
MERGE_SORT(A, l, m)
MERGE_SORT(A, m+1, r)
MERGE(A, l, m, r)
MERGE(A, l, m, r)
create L = A[l..m], R = A[m+1..r]
i = 0, j = 0, k = l
while i < length(L) and j < length(R)
if L[i] <= R[j]: A[k] = L[i]; i++
else: A[k] = R[j]; j++
k++
copy any remaining elements of L and R into A
Worked Examples
Example 1: Input = [95, 83, 98, 87, 81, 92, 89, 100, 85, 91]
Divide into: [95, 83, 98, 87, 81] and [92, 89, 100, 85, 91]
Sorted halves: [81, 83, 87, 95, 98] and [85, 89, 91, 92, 100]
Final merge: [81, 83, 85, 87, 89, 91, 92, 95, 98, 100]
Example 2: Input = [88, 99, 82, 94, 86, 97, 90, 81, 93, 84]
Divide into: [88, 99, 82, 94, 86] and [97, 90, 81, 93, 84]
Sorted halves: [82, 86, 88, 94, 99] and [81, 84, 90, 93, 97]
Final merge: [81, 82, 84, 86, 88, 90, 93, 94, 97, 99]
Example 3: Input = [100, 85, 96, 89, 82, 93, 87, 98, 83, 91]
Divide into: [100, 85, 96, 89, 82] and [93, 87, 98, 83, 91]
Sorted halves: [82, 85, 89, 96, 100] and [83, 87, 91, 93, 98]
Final merge: [82, 83, 85, 87, 89, 91, 93, 96, 98, 100]
Time & Space Complexity
Best Case Average Case Worst Case Space Complexity
O(n log n) O(n log n) O(n log n) O(n)
Always splits into log n levels; merging at each level costs O(n) total, giving O(n log n) in every case regardless of
input arrangement. Needs O(n) auxiliary space for merging. Stable; good for linked lists and external sorting.
(f) Quick Sort
Quick Sort picks a pivot, partitions the array so smaller elements go left and larger go right, and
recursively sorts each partition. (Pivot = last element, Lomuto partition scheme.)
Pseudocode
QUICK_SORT(A, low, high)
if low < high
pi = PARTITION(A, low, high)
QUICK_SORT(A, low, pi-1)
QUICK_SORT(A, pi+1, high)
PARTITION(A, low, high)
pivot = A[high]
i = low - 1
for j = low to high-1
if A[j] <= pivot
i = i + 1
swap(A[i], A[j])
swap(A[i+1], A[high])
return i + 1
Worked Examples
Example 1: Input = [115, 103, 118, 107, 101, 112, 109, 120, 105, 111]
Partition on pivot=111: [103, 107, 101, 109, 105, 111, 115, 120, 118, 112]
Partition on pivot=105: [103, 101, 105, 109, 107, 111, 115, 120, 118, 112]
Partition on pivot=101: [101, 103, 105, 109, 107, 111, 115, 120, 118, 112]
Partition on pivot=107: [101, 103, 105, 107, 109, 111, 115, 120, 118, 112]
Partition on pivot=112: [101, 103, 105, 107, 109, 111, 112, 120, 118, 115]
Partition on pivot=115: [101, 103, 105, 107, 109, 111, 112, 115, 118, 120]
Partition on pivot=120: [101, 103, 105, 107, 109, 111, 112, 115, 118, 120]
Example 2: Input = [108, 119, 102, 114, 106, 117, 110, 101, 113, 104]
Partition on pivot=104: [102, 101, 104, 114, 106, 117, 110, 119, 113, 108]
Partition on pivot=101: [101, 102, 104, 114, 106, 117, 110, 119, 113, 108]
Partition on pivot=108: [101, 102, 104, 106, 108, 117, 110, 119, 113, 114]
Partition on pivot=114: [101, 102, 104, 106, 108, 110, 113, 114, 117, 119]
Partition on pivot=113: [101, 102, 104, 106, 108, 110, 113, 114, 117, 119]
Partition on pivot=119: [101, 102, 104, 106, 108, 110, 113, 114, 117, 119]
Example 3: Input = [120, 105, 116, 109, 102, 113, 107, 118, 103, 111]
Partition on pivot=111: [105, 109, 102, 107, 103, 111, 120, 118, 116, 113]
Partition on pivot=103: [102, 103, 105, 107, 109, 111, 120, 118, 116, 113]
Partition on pivot=109: [102, 103, 105, 107, 109, 111, 120, 118, 116, 113]
Partition on pivot=107: [102, 103, 105, 107, 109, 111, 120, 118, 116, 113]
Partition on pivot=113: [102, 103, 105, 107, 109, 111, 113, 118, 116, 120]
Partition on pivot=120: [102, 103, 105, 107, 109, 111, 113, 118, 116, 120]
Partition on pivot=116: [102, 103, 105, 107, 109, 111, 113, 116, 118, 120]
Time & Space Complexity
Best Case Average Case Worst Case Space Complexity
O(n log n) O(n log n) O(n²) O(log n)
Balanced partitions give O(n log n) (best/average). Worst case O(n²) when the pivot is always smallest/largest (e.g.
sorted input). O(log n) recursion-stack space typically; not stable but fast in practice due to cache locality.
(g) Heap Sort
Heap Sort builds a max-heap from the array, then repeatedly swaps the root (largest) with the last
unsorted element, shrinks the heap, and re-heapifies.
Pseudocode
HEAP_SORT(A, n)
// Build max heap
for i = n/2 - 1 downto 0
HEAPIFY(A, n, i)
// Extract elements one by one
for i = n-1 downto 1
swap(A[0], A[i])
HEAPIFY(A, i, 0)
HEAPIFY(A, n, i)
largest = i
l = 2*i + 1, r = 2*i + 2
if l < n and A[l] > A[largest]: largest = l
if r < n and A[r] > A[largest]: largest = r
if largest != i
swap(A[i], A[largest])
HEAPIFY(A, n, largest)
Worked Examples
Example 1: Input = [135, 123, 138, 127, 121, 132, 129, 140, 125, 131]
Build max-heap: [140, 135, 138, 127, 131, 132, 129, 123, 125, 121]
Extract 140 → heapify: [138, 135, 132, 127, 131, 121, 129, 123, 125, 140]
Extract 138 → heapify: [135, 131, 132, 127, 125, 121, 129, 123, 138, 140]
Extract 135 → heapify: [132, 131, 129, 127, 125, 121, 123, 135, 138, 140]
Extract 132 → heapify: [131, 127, 129, 123, 125, 121, 132, 135, 138, 140]
Extract 131 → heapify: [129, 127, 121, 123, 125, 131, 132, 135, 138, 140]
Extract 129 → heapify: [127, 125, 121, 123, 129, 131, 132, 135, 138, 140]
Extract 127 → heapify: [125, 123, 121, 127, 129, 131, 132, 135, 138, 140]
Extract 125 → heapify: [123, 121, 125, 127, 129, 131, 132, 135, 138, 140]
Extract 123 → final: [121, 123, 125, 127, 129, 131, 132, 135, 138, 140]
Example 2: Input = [128, 139, 122, 134, 126, 137, 130, 121, 133, 124]
Build max-heap: [139, 134, 137, 133, 126, 122, 130, 121, 128, 124]
Extract 139 → heapify: [137, 134, 130, 133, 126, 122, 124, 121, 128, 139]
Extract 137 → heapify: [134, 133, 130, 128, 126, 122, 124, 121, 137, 139]
Extract 134 → heapify: [133, 128, 130, 121, 126, 122, 124, 134, 137, 139]
Extract 133 → heapify: [130, 128, 124, 121, 126, 122, 133, 134, 137, 139]
Extract 130 → heapify: [128, 126, 124, 121, 122, 130, 133, 134, 137, 139]
Extract 128 → heapify: [126, 122, 124, 121, 128, 130, 133, 134, 137, 139]
Extract 126 → heapify: [124, 122, 121, 126, 128, 130, 133, 134, 137, 139]
Extract 124 → heapify: [122, 121, 124, 126, 128, 130, 133, 134, 137, 139]
Extract 122 → final: [121, 122, 124, 126, 128, 130, 133, 134, 137, 139]
Example 3: Input = [140, 125, 136, 129, 122, 133, 127, 138, 123, 131]
Build max-heap: [140, 138, 136, 129, 131, 133, 127, 125, 123, 122]
Extract 140 → heapify: [138, 131, 136, 129, 122, 133, 127, 125, 123, 140]
Extract 138 → heapify: [136, 131, 133, 129, 122, 123, 127, 125, 138, 140]
Extract 136 → heapify: [133, 131, 127, 129, 122, 123, 125, 136, 138, 140]
Extract 133 → heapify: [131, 129, 127, 125, 122, 123, 133, 136, 138, 140]
Extract 131 → heapify: [129, 125, 127, 123, 122, 131, 133, 136, 138, 140]
Extract 129 → heapify: [127, 125, 122, 123, 129, 131, 133, 136, 138, 140]
Extract 127 → heapify: [125, 123, 122, 127, 129, 131, 133, 136, 138, 140]
Extract 125 → heapify: [123, 122, 125, 127, 129, 131, 133, 136, 138, 140]
Extract 123 → final: [122, 123, 125, 127, 129, 131, 133, 136, 138, 140]
Time & Space Complexity
Best Case Average Case Worst Case Space Complexity
O(n log n) O(n log n) O(n log n) O(1)
Building the heap is O(n); each of n extractions costs O(log n) — giving O(n log n) in every case, independent of
input arrangement. O(1) auxiliary space (more space-efficient than Merge Sort); not stable.
Part 1 Summary — Non-Linear Sorting
Algorithm Best Average Worst Space Stable?
Bubble Sort O(n) O(n²) O(n²) O(1) Yes
Selection Sort O(n²) O(n²) O(n²) O(1) No
Insertion Sort O(n) O(n²) O(n²) O(1) Yes
Shell Sort O(n log n) ≈O(n^1.25) O(n²) O(1) No
Merge Sort O(n log n) O(n log n) O(n log n) O(n) Yes
Quick Sort O(n log n) O(n log n) O(n²) O(log n) No
Heap Sort O(n log n) O(n log n) O(n log n) O(1) No
PART 2 — LINEAR SORTING ALGORITHMS
(a) Counting Sort
Counting Sort works on integers within a known range [0, k]. It counts occurrences of each value,
converts counts into cumulative (prefix-sum) positions, and places each element directly into its correct
output position — no element comparisons are made.
Pseudocode
COUNTING_SORT(A, n, k) // k = maximum value in A
let Count[0..k] = 0
for i = 0 to n-1
Count[A[i]] = Count[A[i]] + 1 // Step 1: frequency count
for i = 1 to k
Count[i] = Count[i] + Count[i-1] // Step 2: cumulative (prefix) sum
let Output[0..n-1]
for i = n-1 downto 0 // Step 3: place elements (stable)
Output[Count[A[i]] - 1] = A[i]
Count[A[i]] = Count[A[i]] - 1
return Output
Worked Examples
Example 1: Input = [4, 2, 7, 4, 1, 9, 2, 6, 3, 8]
Frequency (Count) array, index 0 to 9: [0, 1, 2, 1, 2, 0, 1, 1, 1, 1]
Cumulative (prefix-sum) Count array: [0, 1, 3, 4, 6, 6, 7, 8, 9, 10]
Output array (built right-to-left using Count): [1, 2, 2, 3, 4, 4, 6, 7, 8, 9]
Example 2: Input = [1, 5, 3, 8, 1, 6, 4, 9, 2, 7]
Frequency (Count) array, index 0 to 9: [0, 2, 1, 1, 1, 1, 1, 1, 1, 1]
Cumulative (prefix-sum) Count array: [0, 2, 3, 4, 5, 6, 7, 8, 9, 10]
Output array (built right-to-left using Count): [1, 1, 2, 3, 4, 5, 6, 7, 8, 9]
Example 3: Input = [9, 3, 6, 1, 8, 2, 9, 5, 0, 4]
Frequency (Count) array, index 0 to 9: [1, 1, 1, 1, 1, 1, 1, 0, 1, 2]
Cumulative (prefix-sum) Count array: [1, 2, 3, 4, 5, 6, 7, 7, 8, 10]
Output array (built right-to-left using Count): [0, 1, 2, 3, 4, 5, 6, 8, 9, 9]
Time & Space Complexity
Best Case Average Case Worst Case Space Complexity
O(n + k) O(n + k) O(n + k) O(n + k)
Frequency counting is O(n), cumulative sum is O(k), placement is O(n) — giving O(n + k) in every case, regardless of
input order. Space O(n + k) for Count and Output arrays. Stable; inefficient when k ≫ n.
(b) Radix Sort
Radix Sort sorts multi-digit numbers digit by digit, from Least Significant Digit (LSD) to Most Significant
Digit, using a stable Counting Sort at each digit position.
Pseudocode
RADIX_SORT(A, n)
max = maximum value in A
for exp = 1; max / exp > 0; exp = exp * 10 // exp = 1, 10, 100, ...
COUNTING_SORT_BY_DIGIT(A, n, exp)
return A
COUNTING_SORT_BY_DIGIT(A, n, exp) // stable sort by digit at place value
'exp'
let Output[0..n-1]
let Count[0..9] = 0
for i = 0 to n-1
digit = (A[i] / exp) mod 10
Count[digit] = Count[digit] + 1
for i = 1 to 9
Count[i] = Count[i] + Count[i-1]
for i = n-1 downto 0
digit = (A[i] / exp) mod 10
Output[Count[digit] - 1] = A[i]
Count[digit] = Count[digit] - 1
copy Output back into A
Worked Examples
Example 1: Input = [329, 457, 657, 839, 436, 720, 355, 612, 928, 271]
After sorting by units digit (exp=1): [720, 271, 612, 355, 436, 457, 657, 928, 329, 839]
After sorting by tens digit (exp=10): [612, 720, 928, 329, 436, 839, 355, 457, 657, 271]
After sorting by hundreds digit (exp=100): [271, 329, 355, 436, 457, 612, 657, 720, 839,
928]
Example 2: Input = [201, 127, 45, 88, 9, 512, 333, 764, 890, 156]
After sorting by units digit (exp=1): [890, 201, 512, 333, 764, 45, 156, 127, 88, 9]
After sorting by tens digit (exp=10): [201, 9, 512, 127, 333, 45, 156, 764, 88, 890]
After sorting by hundreds digit (exp=100): [9, 45, 88, 127, 156, 201, 333, 512, 764, 890]
Example 3: Input = [841, 273, 619, 405, 738, 92, 517, 660, 234, 981]
After sorting by units digit (exp=1): [660, 841, 981, 92, 273, 234, 405, 517, 738, 619]
After sorting by tens digit (exp=10): [405, 517, 619, 234, 738, 841, 660, 273, 981, 92]
After sorting by hundreds digit (exp=100): [92, 234, 273, 405, 517, 619, 660, 738, 841,
981]
Time & Space Complexity
Best Case Average Case Worst Case Space Complexity
O(d·(n + b)) O(d·(n + b)) O(d·(n + b)) O(n + b)
Each of d digit positions runs one Counting Sort pass costing O(n + b), b=10 — total O(d·(n + b)), same for every
case. With d treated as a small constant, this is effectively O(n). Space O(n + b). Stable if the digit-wise sort is
stable.
(c) Bucket Sort
Bucket Sort distributes n elements (assumed uniformly distributed over [0, 1)) into n buckets, sorts each
bucket individually (e.g. Insertion Sort), then concatenates the sorted buckets.
Pseudocode
BUCKET_SORT(A, n) // assumes A[i] is a real number in [0, 1)
create n empty buckets B[0..n-1]
for i = 0 to n-1
idx = floor(n * A[i]) // Step 1: scatter into buckets
insert A[i] into B[idx]
for i = 0 to n-1
INSERTION_SORT(B[i]) // Step 2: sort each bucket
result = concatenate B[0], B[1], ..., B[n-1] in order // Step 3: gather
return result
Worked Examples
Example 1: Input = [0.42, 0.32, 0.23, 0.52, 0.25, 0.47, 0.51, 0.68, 0.71, 0.09]
Bucket 0 (range [0.00, 0.10)): [0.09]
Bucket 2 (range [0.20, 0.30)): [0.23, 0.25]
Bucket 3 (range [0.30, 0.40)): [0.32]
Bucket 4 (range [0.40, 0.50)): [0.42, 0.47]
Bucket 5 (range [0.50, 0.60)): [0.52, 0.51]
Bucket 6 (range [0.60, 0.70)): [0.68]
Bucket 7 (range [0.70, 0.80)): [0.71]
Bucket 0 sorted: [0.09]
Bucket 2 sorted: [0.23, 0.25]
Bucket 3 sorted: [0.32]
Bucket 4 sorted: [0.42, 0.47]
Bucket 5 sorted: [0.51, 0.52]
Bucket 6 sorted: [0.68]
Bucket 7 sorted: [0.71]
Final concatenated result: [0.09, 0.23, 0.25, 0.32, 0.42, 0.47, 0.51, 0.52, 0.68,
0.71]
Example 2: Input = [0.78, 0.17, 0.39, 0.72, 0.94, 0.21, 0.12, 0.55, 0.63, 0.08]
Bucket 0 (range [0.00, 0.10)): [0.08]
Bucket 1 (range [0.10, 0.20)): [0.17, 0.12]
Bucket 2 (range [0.20, 0.30)): [0.21]
Bucket 3 (range [0.30, 0.40)): [0.39]
Bucket 5 (range [0.50, 0.60)): [0.55]
Bucket 6 (range [0.60, 0.70)): [0.63]
Bucket 7 (range [0.70, 0.80)): [0.78, 0.72]
Bucket 9 (range [0.90, 1.00)): [0.94]
Bucket 0 sorted: [0.08]
Bucket 1 sorted: [0.12, 0.17]
Bucket 2 sorted: [0.21]
Bucket 3 sorted: [0.39]
Bucket 5 sorted: [0.55]
Bucket 6 sorted: [0.63]
Bucket 7 sorted: [0.72, 0.78]
Bucket 9 sorted: [0.94]
Final concatenated result: [0.08, 0.12, 0.17, 0.21, 0.39, 0.55, 0.63, 0.72, 0.78,
0.94]
Example 3: Input = [0.63, 0.11, 0.25, 0.89, 0.45, 0.36, 0.75, 0.92, 0.14, 0.58]
Bucket 1 (range [0.10, 0.20)): [0.11, 0.14]
Bucket 2 (range [0.20, 0.30)): [0.25]
Bucket 3 (range [0.30, 0.40)): [0.36]
Bucket 4 (range [0.40, 0.50)): [0.45]
Bucket 5 (range [0.50, 0.60)): [0.58]
Bucket 6 (range [0.60, 0.70)): [0.63]
Bucket 7 (range [0.70, 0.80)): [0.75]
Bucket 8 (range [0.80, 0.90)): [0.89]
Bucket 9 (range [0.90, 1.00)): [0.92]
Bucket 1 sorted: [0.11, 0.14]
Bucket 2 sorted: [0.25]
Bucket 3 sorted: [0.36]
Bucket 4 sorted: [0.45]
Bucket 5 sorted: [0.58]
Bucket 6 sorted: [0.63]
Bucket 7 sorted: [0.75]
Bucket 8 sorted: [0.89]
Bucket 9 sorted: [0.92]
Final concatenated result: [0.11, 0.14, 0.25, 0.36, 0.45, 0.58, 0.63, 0.75, 0.89,
0.92]
Time & Space Complexity
Best Case Average Case Worst Case Space Complexity
O(n + k) O(n + k) O(n²) O(n + k)
Scattering and gathering are each O(n). With uniform distribution, each bucket gets O(1) elements, so best/average
is O(n + k) ≈ O(n). Worst case O(n²) occurs when all elements fall into one bucket. Space O(n + k). Stable if the per-
bucket sort is stable.
Part 2 Summary — Linear Sorting
Algorithm Best Average Worst Space
Counting Sort O(n+k) O(n+k) O(n+k) O(n+k)
Radix Sort O(d(n+b)) O(d(n+b)) O(d(n+b)) O(n+b)
Bucket Sort O(n+k) O(n+k) O(n²) O(n+k)
k = range of input values, b = base used by Radix Sort (10 for decimal digits), d = number of digits in the largest
number.