Sorting Algorithms: Complexity, Traces and Which Sort to Use · সর্টিং অ্যালগরিদম: জটিলতা, ধাপে ধাপে ট্রেস ও কোন সর্ট কখন

1. What sorting is and the words exams use

Sorting puts items in order, usually ascending. Sorted data makes binary search possible (about 20 comparisons for 1 million items, since 2²⁰ ≈ 1.05 million), and makes duplicates and ranges easy to find. These properties classify every sort:

Property	Meaning	Examples
Comparison sort	Decides order only by comparing two keys	Bubble, selection, insertion, Shell, merge, quick, heap
Non-comparison sort	Uses the key values or digits directly	Counting, radix, bucket
Stable	Equal keys keep their original order	Bubble, insertion, merge, counting, radix
In-place	Needs only O(1) extra memory (quick sort's O(log n) stack is usually accepted)	Bubble, selection, insertion, heap, quick
Adaptive	Runs faster on nearly sorted input	Insertion, bubble with a "no swap" check

All traces below sort the same array, [5, 8, 3, 6, 2], into ascending order, so you can compare the algorithms directly.

2. Bubble sort

Compare each adjacent pair and swap it if it is out of order. After pass 1 the largest item has "bubbled" to the end; each later pass fixes one more item. Stop early if a pass makes no swap.

Worked example 1: how many swaps does bubble sort need for 5, 8, 3, 6, 2?

Pass	Comparisons and swaps	Array after the pass	Swaps
1	(5,8) no; (8,3) swap; (8,6) swap; (8,2) swap	[5, 3, 6, 2, 8]	3
2	(5,3) swap; (5,6) no; (6,2) swap	[3, 5, 2, 6, 8]	2
3	(3,5) no; (5,2) swap	[3, 2, 5, 6, 8]	1
4	(3,2) swap	[2, 3, 5, 6, 8]	1

Total: 7 swaps and 4 + 3 + 2 + 1 = 10 comparisons in 4 passes; bubble sort never needs more than n − 1 passes. Shortcut: bubble sort makes exactly one swap per inversion (a pair out of order). The inversions here are (5,3), (5,2), (8,3), (8,6), (8,2), (3,2), (6,2): 7.

#include <stdio.h>

int main(void) {
    int a[] = {5, 8, 3, 6, 2};
    int n = sizeof a / sizeof a[0];
    int swaps = 0;

    for (int i = 0; i < n - 1; i++) {
        int swapped = 0;
        for (int j = 0; j < n - 1 - i; j++) {
            if (a[j] > a[j + 1]) {          /* out of order: swap */
                int t = a[j]; a[j] = a[j + 1]; a[j + 1] = t;
                swaps++;
                swapped = 1;
            }
        }
        if (!swapped) break;                /* no swap: already sorted */
    }
    for (int i = 0; i < n; i++) printf("%d ", a[i]);
    printf("\nswaps = %d\n", swaps);
    return 0;
}

Output: 2 3 5 6 8 and swaps = 7. Comparisons in the worst case: (n − 1) + (n − 2) + … + 1 = n(n − 1)/2, so O(n²). With the early stop, an already sorted array needs one pass of n − 1 comparisons: best case O(n).

3. Selection sort

Find the minimum of the unsorted part and swap it to the front.

Pass	Minimum of the unsorted part	Array after the pass
1	2 (swap with 5)	[2, 8, 3, 6, 5]
2	3 (swap with 8)	[2, 3, 8, 6, 5]
3	5 (swap with 8)	[2, 3, 5, 6, 8]
4	6 (already in place)	[2, 3, 5, 6, 8]

Only 3 swaps (at most n − 1 ever), which helps when moving items is expensive. But it always scans the whole unsorted part, so it makes n(n − 1)/2 comparisons in every case: O(n²) best, average and worst. It is not stable: on [4ᵃ, 4ᵇ, 1], pass 1 swaps 1 with 4ᵃ, giving [1, 4ᵇ, 4ᵃ].

4. Insertion sort

Like sorting cards in your hand: take the next item (the key) and shift bigger items in the sorted left part one step right until the key fits.

Pass	Key	Array after inserting it
1	8	[5, 8, 3, 6, 2]
2	3	[3, 5, 8, 6, 2]
3	6	[3, 5, 6, 8, 2]
4	2	[2, 3, 5, 6, 8]

This took 7 shifts and 9 comparisons. Worst case (reverse order): n(n − 1)/2 comparisons, 10 for n = 5. Best case (already sorted): n − 1 comparisons, O(n). It is stable, in-place and adaptive, and the fastest simple sort for small or nearly sorted arrays.

Shell sort

Insertion sort moves an item only one place per shift. Shell sort (Donald Shell, 1959) first runs insertion sort on items a gap apart, then on smaller gaps, and ends with gap 1, which is ordinary insertion sort on an almost sorted array. Common gap sequences: Shell's n/2, n/4, …, 1 and Knuth's 1, 4, 13, 40, … (h = 3h + 1, used largest first).

Gap	What happens	Array after the pass
2	Sort positions 0, 2, 4 (5, 3, 2 → 2, 3, 5) and positions 1, 3 (8, 6 → 6, 8)	[2, 6, 3, 8, 5]
1	Ordinary insertion sort: only 3 shifts, because 2 is already at the front	[2, 3, 5, 6, 8]

Shell sort is in-place but not stable (gap 2 on [4ᵃ, 4ᵇ, 1] gives [1, 4ᵇ, 4ᵃ]). Its time depends on the gaps: worst case O(n²) with Shell's halving gaps, O(n√n) with Knuth's, and about O(n log n) at best on sorted input.

5. Merge sort (divide and conquer)

Split the array in half, sort each half recursively, then merge the two sorted halves by repeatedly taking the smaller front item. Merging two sorted lists of total length n takes at most n − 1 comparisons: O(n).

Where T(n) = 2T(n/2) + n comes from. Sorting n items means sorting two halves of n/2 items (2T(n/2)) and merging them (about n steps). Unrolling it, with n = 2ᵏ and T(1) = 0:

T(n) = 2T(n/2) + n = 4T(n/4) + 2n = 8T(n/8) + 3n = … = 2ᵏ·T(1) + k·n = n log₂ n.

There are log₂ n levels and each level does n work in total. Checked by computing the recurrence: T(8) = 24 = 8 × 3 and T(1024) = 10,240 = 1024 × 10. So merge sort is Θ(n log n) in every case, is stable, needs O(n) extra memory, and suits linked lists and external sorting (data larger than memory, such as 1 GB with 100 MB of RAM: sort chunks that fit, then merge them).

6. Quick sort and its O(n²) worst case

Choose a pivot, partition so smaller items go left and larger go right (the pivot lands in its final place), then quick sort each side. Average O(n log n) and usually the fastest in practice (in place, cache friendly); not stable.

Worked example 2: partition [5, 8, 3, 6, 2] with the first element as pivot.

1. Pivot = 5. Index i moves right from 8 looking for an item > 5: stops at 8. Index j moves left from 2 looking for an item ≤ 5: stops at 2. Swap them: [5, 2, 3, 6, 8].
2. i moves on: 3 ≤ 5, then stops at 6. j moves left: 8 and 6 are > 5, stops at 3. Now i has passed j, so stop.
3. Swap the pivot with a[j] (the 3): [3, 2, 5, 6, 8]. 5 is in its final position, with [3, 2] on the left and [6, 8] on the right.
4. Left part [3, 2], pivot 3 → [2, 3]. Right part [6, 8], pivot 6 → unchanged. Result [2, 3, 5, 6, 8].

Why the worst case is O(n²). Run the same code on the already sorted [2, 3, 5, 6, 8]: pivot 2 is the smallest, so the parts have sizes 0 and 4; then pivot 3 leaves 0 and 3, and so on. Each partition removes only the pivot, so the comparisons are 4 + 3 + 2 + 1 = 10 = n(n − 1)/2. In general T(n) = T(n − 1) + n = O(n²), with recursion depth n (so O(n) stack). Counted in a test: 1,000 already sorted numbers took 499,500 comparisons; 1,000 random numbers took about 11,000 on average (n log₂ n ≈ 9,966).

With balanced splits, T(n) = 2T(n/2) + n = O(n log n), the best and average case. A random or median-of-three pivot makes the worst case very unlikely but not impossible: randomized quick sort is still O(n²) in the worst case, with O(n log n) expected time.

Point	Quick sort	Merge sort
Method	Divide and conquer; work done while partitioning	Divide and conquer; work done while merging
Best / average	O(n log n)	O(n log n)
Worst	O(n²)	O(n log n)
Extra space	O(log n) stack on average, O(n) worst	O(n) array
Stable	No	Yes
Preferred for	Arrays in memory (fast in practice)	Guaranteed time, stability, linked lists, external sorting

7. Heap sort

Build a max-heap (every parent ≥ its children; stored in an array where the children of index i are 2i + 1 and 2i + 2). Then repeatedly swap the root (the maximum) with the last item of the heap, shrink the heap by one, and sift the new root down.

Step	Heap part + sorted part
Build max-heap	[8, 6, 3, 5, 2]
Move 8 to the end, sift down	[6, 5, 3, 2] + [8]
Move 6	[5, 2, 3] + [6, 8]
Move 5	[3, 2] + [5, 6, 8]
Move 3	[2] + [3, 5, 6, 8]

Building the heap takes O(n); each of the n − 1 extractions takes O(log n), so heap sort is O(n log n) in every case with O(1) extra memory. It is not stable. With very little extra memory and many items, heap sort is the usual answer.

8. Counting sort and radix sort (non-comparison)

Counting sort (integer keys 0 … k): count each value, turn the counts into running totals (positions), then place items from right to left, which keeps it stable. For [4, 2, 2, 8, 3, 3, 1]: counts of 1, 2, 3, 4, 8 are 1, 2, 2, 1, 1; running totals 1, 3, 5, 6, 7; output [1, 2, 2, 3, 3, 4, 8]. Time and space O(n + k): excellent for a small range, useless for huge k.

Worked example 3: radix sort 608, 5, 768, 298, 576, 975, 90, 80. Sort by one digit at a time, least significant first, with a stable sort at each digit (005 has 0 tens and 0 hundreds).

Pass	Digit	Result
1	Units	90, 80, 5, 975, 576, 608, 768, 298
2	Tens	5, 608, 768, 975, 576, 80, 90, 298
3	Hundreds	5, 80, 90, 298, 576, 608, 768, 975

Time O(d(n + b)) for d digits in base b: linear for fixed-width keys. Stability at each pass is what keeps the earlier digit order.

Bucket sort spreads keys over k buckets by value range, sorts each bucket (usually with insertion sort) and joins the buckets in order: O(n + k) on average for uniformly distributed keys, O(n²) in the worst case when all keys land in one bucket.

9. The complexity table

Algorithm	Best	Average	Worst	Extra space	Stable	In-place
Bubble	O(n) with early stop	O(n²)	O(n²)	O(1)	Yes	Yes
Selection	O(n²)	O(n²)	O(n²)	O(1)	No	Yes
Insertion	O(n)	O(n²)	O(n²)	O(1)	Yes	Yes
Shell	O(n log n)	Depends on the gaps	O(n²) Shell's gaps, O(n√n) Knuth's	O(1)	No	Yes
Merge	O(n log n)	O(n log n)	O(n log n)	O(n)	Yes	No
Quick	O(n log n)	O(n log n)	O(n²)	O(log n) average	No	Yes
Heap	O(n log n)	O(n log n)	O(n log n)	O(1)	No	Yes
Counting	O(n + k)	O(n + k)	O(n + k)	O(n + k)	Yes	No
Radix	O(d(n + b))	O(d(n + b))	O(d(n + b))	O(n + b)	Yes	No
Bucket	O(n + k)	O(n + k) uniform keys	O(n²)	O(n + k)	Yes, with insertion sort in buckets	No

10. Which sort for which case

Situation	Best choice	Why
Nearly sorted data, such as {1, 2, 3, 8, 15, 10}	Insertion, or bubble with early stop	O(n) when almost sorted: bubble needs 9 comparisons and 1 swap here
Small arrays (about 10–20 items)	Insertion	Low overhead; libraries use it inside merge and quick sort
General in-memory sorting, speed matters	Quick sort	Fastest on average
Guaranteed O(n log n) and stability	Merge sort	Same time in every case
Very little extra memory, guaranteed O(n log n)	Heap sort	In place, no O(n²) case
Linked list	Merge sort	Needs only sequential access, no extra array
Data bigger than RAM	External merge sort	Sorts chunks, then merges runs
Expensive moves (large records)	Selection	At most n − 1 swaps
Integers in a small range (marks 0–100)	Counting	O(n + k)
Fixed-length numbers or strings	Radix	Linear for fixed width
Time least dependent on input order	Merge, selection (also heap)	Same work on sorted, reversed and random input

Real libraries: Python's sorted() and list.sort() use Timsort (a merge–insertion hybrid, guaranteed stable); Java's Arrays.sort uses a dual-pivot quick sort for primitive arrays and a stable merge sort (Timsort) for objects; C's qsort() is not guaranteed to be stable (the C standard leaves the order of equal elements unspecified).

11. The Ω(n log n) lower bound for comparison sorts

Any comparison sort can be drawn as a decision tree: each inner node is a comparison, each leaf is one possible ordering of the input. To sort every input correctly, the tree needs at least n! leaves. A binary tree of height h has at most 2ʰ leaves, so 2ʰ ≥ n!, giving h ≥ log₂(n!) = Θ(n log n). The height is the worst-case number of comparisons, so every comparison sort needs Ω(n log n) comparisons in the worst case. Merge sort and heap sort are therefore asymptotically optimal.

Minimum worst-case comparisons by this bound: n = 3 → ⌈log₂ 6⌉ = 3; n = 5 → ⌈log₂ 120⌉ = 7; n = 10 → ⌈log₂ 3,628,800⌉ = 22. Counting and radix sort are faster than n log n without contradicting this, because they never compare two keys; they rely on keys being small integers or fixed-length digit strings.

12. Tricky exam cases

• "Which sort uses divide and conquer?" Merge sort and quick sort (quick sort is not greedy and not dynamic programming).
• "Which is fastest?" Quick sort on average among general sorts; for nearly sorted input, insertion (or bubble with early stop).
• Insertion sort worst-case comparisons = n(n − 1)/2; bubble sort makes O(n²) comparisons.
• Not comparison based: counting, radix, bucket. Method for proving sorting lower bounds: the decision tree.
• Not stable in the typical form: selection, Shell, quick and heap sort.
• Randomized quick sort has expected O(n log n) but worst case O(n²).
• "Time taken by an NP-class (non-deterministic) sorting algorithm" is keyed O(n): it can guess each item's position and check the result in one pass.
• Topological sort is not a sorting of values: it orders the vertices of a directed acyclic graph (DAG) so every edge u → v has u before v, in O(V + E). A graph with a cycle has no topological order.
• Merging two sorted lists of sizes m and n takes O(m + n): each comparison outputs one item.