Sorting Algorithms — Ananta Code Academy

🪀 Bubble Sort

Repeatedly swap adjacent elements that are in the wrong order

O(n²)

Bubble Sort is the simplest sorting algorithm. It makes multiple passes through the array. On each pass, it compares neighbouring pairs and swaps them if they are in the wrong order. After each pass, the largest unsorted element "bubbles up" to its correct position at the right end. The algorithm needs at most n-1 passes to fully sort an array of n elements.

1
Start from the leftmost element. Compare element at index i with element at index i+1.
2
If arr[i] > arr[i+1] — swap them. The bigger element moves right.
3
Move to the next pair (i+1 and i+2) and repeat. Continue to the end of the unsorted portion.
4
After one full pass, the largest element is at its final position. Reduce the inner loop range by 1.
5
Repeat passes until no swaps occur in a pass — the array is sorted.

array: [64, 34, 25, 12, 22] — after each pass

        Pass 1: [34, 25, 12, 22, 64]  ← 64 bubbled to end

        Pass 2: [25, 12, 22, 34, 64]  ← 34 in place

        Pass 3: [12, 22, 25, 34, 64]  ← 25 in place

        Pass 4: [12, 22, 25, 34, 64]  ← sorted ✓

bubble_sort.c

void bubbleSort(int arr[], int n) {
    for (int i = 0; i < n-1; i++) {
        int swapped = 0;
        for (int j = 0; j < n-i-1; j++) {   /* inner loop shrinks each pass */
            if (arr[j] > arr[j+1]) {
                int tmp = arr[j]; arr[j] = arr[j+1]; arr[j+1] = tmp;
                swapped = 1;
            }
        }
        if (!swapped) break;  /* already sorted — early exit */
    }
}

Case	Time	Explanation
Best	O(n)	Already sorted — one pass, zero swaps, early exit
Average	O(n²)	Random input — roughly n²/4 comparisons
Worst	O(n²)	Reverse-sorted — maximum n²/2 swaps
Space	O(1)	In-place — only one temp variable for swapping

When to use: Almost never in production. Its only real advantage is the early-exit optimisation — it detects an already-sorted array in O(n). Good for teaching and for tiny arrays (< 10 elements) where simplicity matters more than speed.

algorithm 2

🔍 Selection Sort

Find the minimum in the unsorted part, swap it to the front

O(n²)

Selection Sort divides the array into a sorted left part and an unsorted right part. On each pass it scans the entire unsorted portion to find the minimum element, then swaps it into position at the boundary. The boundary moves right by one after each pass. Unlike Bubble Sort, it makes exactly n-1 swaps regardless of input — only the number of comparisons varies.

1
Set the current position i (starts at 0) as the candidate for the minimum.
2
Scan from i+1 to end. If any element is smaller than current min, update minIdx.
3
Swap arr[i] with arr[minIdx] — the true minimum lands in its correct position.
4
Move i forward by 1. Sorted region grows. Repeat until i == n-1.

array: [64, 25, 12, 22, 11] — each pass places one minimum

        Pass 1: [11, 25, 12, 22, 64]  ← min=11, swapped with 64

        Pass 2: [11, 12, 25, 22, 64]  ← min=12, swapped with 25

        Pass 3: [11, 12, 22, 25, 64]  ← min=22, swapped with 25

        Pass 4: [11, 12, 22, 25, 64]  ← sorted ✓

selection_sort.c

void selectionSort(int arr[], int n) {
    for (int i = 0; i < n-1; i++) {
        int minIdx = i;
        for (int j = i+1; j < n; j++)   /* find minimum in unsorted part */
            if (arr[j] < arr[minIdx]) minIdx = j;

        if (minIdx != i) {              /* swap minimum to front */
            int tmp = arr[i]; arr[i] = arr[minIdx]; arr[minIdx] = tmp;
        }
    }
}

Case	Time	Explanation
Best	O(n²)	Always scans the full unsorted portion — no early exit
Average	O(n²)	n(n-1)/2 comparisons always
Worst	O(n²)	Same as average — input order makes no difference
Space	O(1)	In-place — only temp variable for swap

Key advantage: Only n-1 swaps maximum. If swapping is expensive (large structs, slow memory), Selection Sort beats Bubble Sort. It is also simple to understand and easy to implement correctly — good for small arrays and teaching.

algorithm 3

✍️ Insertion Sort

Pick one element and slide it left into its correct position in the sorted part

O(n²) / O(n)

Insertion Sort works like sorting a hand of playing cards. You pick up one card at a time and slide it left into the correct position among the cards you've already sorted. The left part of the array is always sorted. The right part is the "deck" you haven't touched yet. Each step takes one element from the right and inserts it in the right place on the left.

1
Pick element at position i (start at 1). Store it as key.
2
Compare key with elements to its left, shifting each larger element one position right.
3
When you find an element ≤ key (or reach the start), drop key in the gap.
4
Move i forward. Left portion grows by one sorted element. Repeat.

array: [5, 3, 8, 1, 4] — inserting one element at a time

        i=1: key=3  [3, 5, 8, 1, 4]  ← 3 inserted before 5

        i=2: key=8  [3, 5, 8, 1, 4]  ← 8 already in place

        i=3: key=1  [1, 3, 5, 8, 4]  ← 1 slides all the way left

        i=4: key=4  [1, 3, 4, 5, 8]  ← sorted ✓

insertion_sort.c

void insertionSort(int arr[], int n) {
    for (int i = 1; i < n; i++) {
        int key = arr[i];   /* element to insert */
        int j   = i - 1;

        while (j >= 0 && arr[j] > key) {
            arr[j+1] = arr[j];   /* shift right to make room */
            j--;
        }
        arr[j+1] = key;         /* drop key in the gap */
    }
}

Case	Time	Explanation
Best	O(n)	Already sorted — inner while never executes
Average	O(n²)	Random input — roughly n²/4 shifts
Worst	O(n²)	Reverse-sorted — every element shifts all the way left
Space	O(1)	In-place — uses only the key variable

Best of the O(n²) sorts. Insertion Sort is adaptive (faster on nearly-sorted data), stable (equal elements keep their original order), and online (can sort a stream without seeing all data first). Python's timsort and Java's Arrays.sort use Insertion Sort for small subarrays (< 64 elements) inside Merge Sort.

algorithm 4

✂️ Merge Sort

Divide into halves, sort each half recursively, merge them back together

O(n log n)

Merge Sort uses the classic Divide and Conquer strategy. It splits the array in half, sorts each half by calling itself recursively, then merges the two sorted halves into one sorted array. The merge step walks through both halves simultaneously, always picking the smaller of the two front elements. The recursion bottoms out at arrays of size 1 — a single element is trivially sorted.

1
Divide: Find the midpoint mid = (lo + hi) / 2. Split into [lo..mid] and [mid+1..hi].
2
Conquer: Recursively call mergeSort on each half.
3
Merge: Two pointers walk the two sorted halves. Always copy the smaller front element into the output array.
4
Copy any remaining elements from either half. Copy the merged result back into the original array.

divide & conquer on [38, 27, 43, 3]

        Split:   [38, 27] | [43, 3]

        Split:   [38] [27] | [43] [3]    ← base case: size 1

        Merge:   [27, 38] | [3, 43]

        Merge:   [3, 27, 38, 43]             ← sorted ✓

merge_sort.c

void merge(int arr[], int lo, int mid, int hi) {
    int n1 = mid-lo+1, n2 = hi-mid;
    int L[n1], R[n2];

    for (int i=0; i<n1; i++) L[i] = arr[lo+i];
    for (int j=0; j<n2; j++) R[j] = arr[mid+1+j];

    int i=0, j=0, k=lo;
    while (i < n1 && j < n2)
        arr[k++] = (L[i] <= R[j]) ? L[i++] : R[j++]; /* pick smaller */
    while (i < n1) arr[k++] = L[i++];  /* copy leftovers */
    while (j < n2) arr[k++] = R[j++];
}

void mergeSort(int arr[], int lo, int hi) {
    if (lo < hi) {
        int mid = lo + (hi-lo)/2;
        mergeSort(arr, lo,   mid);   /* sort left half  */
        mergeSort(arr, mid+1, hi);   /* sort right half */
        merge(arr, lo, mid, hi);       /* merge both      */
    }
}

Case	Time	Explanation
Best	O(n log n)	Always divides log n levels deep, n work per level
Average	O(n log n)	Input order doesn't matter — same structure always
Worst	O(n log n)	Guaranteed regardless of input
Space	O(n)	Needs temporary arrays for the merge step

When to use: When you need guaranteed O(n log n) and stability (equal elements keep their order). Merge Sort is the algorithm behind Java's Arrays.sort for objects and Python's sorted(). Its only downside is the O(n) extra memory. Excellent for linked lists — no extra memory needed.

algorithm 5

⚡ Quick Sort

Pick a pivot, partition around it, recurse on each side

O(n log n) avg

Quick Sort is typically the fastest sorting algorithm in practice. It picks a pivot element, then rearranges the array so that all elements smaller than the pivot are to its left and all elements larger are to its right. The pivot is now in its final sorted position. Quick Sort then recurses on the left and right sub-arrays. No merging needed — all work happens during partitioning.

1
Choose a pivot (last element is simplest). Initialise i = lo - 1 (boundary of "small" zone).
2
Walk j from lo to hi-1. When arr[j] <= pivot, advance i and swap arr[i] with arr[j].
3
After the loop, swap pivot (arr[hi]) with arr[i+1]. Pivot is now in its correct final position.
4
Return the pivot's index. Recurse on [lo .. pivot-1] and [pivot+1 .. hi].

partitioning [10, 80, 30, 90, 40, 50, 70] with pivot=70

        Elements < 70: 10, 30, 40, 50    Elements > 70: 80, 90

        After partition: [10, 30, 40, 50, 70, 80, 90]

        ↪ Recurse left: [10,30,40,50]   Recurse right: [80,90]

quick_sort.c

int partition(int arr[], int lo, int hi) {
    int pivot = arr[hi];    /* last element as pivot */
    int i = lo - 1;

    for (int j = lo; j < hi; j++) {
        if (arr[j] <= pivot) {
            i++;
            int tmp = arr[i]; arr[i] = arr[j]; arr[j] = tmp;
        }
    }
    /* place pivot in final position */
    int tmp = arr[i+1]; arr[i+1] = arr[hi]; arr[hi] = tmp;
    return i + 1;
}

void quickSort(int arr[], int lo, int hi) {
    if (lo < hi) {
        int pi = partition(arr, lo, hi);
        quickSort(arr, lo,    pi-1);  /* left of pivot  */
        quickSort(arr, pi+1, hi);     /* right of pivot */
    }
}

Case	Time	Explanation
Best	O(n log n)	Pivot always divides array in half
Average	O(n log n)	Random pivot is near-middle on average
Worst	O(n²)	Pivot is always smallest or largest (sorted input with last-element pivot)
Space	O(log n)	Recursive call stack — no extra array

Worst case O(n²) occurs when the pivot is always the smallest or largest element — e.g. sorted input with a naive last-element pivot. Fix: use median-of-three pivot or random pivot. C's standard qsort() and most implementations use randomised Quick Sort and are O(n log n) in practice.

algorithm 6

🔢 Counting Sort

Count occurrences, compute positions, place elements directly — no comparisons

O(n + k)

Counting Sort is a non-comparison sort — it never compares elements against each other. It works by counting how many times each value appears, then using those counts to calculate the exact position where each element belongs in the output. It is faster than any comparison-based sort when the range of values k is not much larger than the number of elements n.

1
Find the maximum value k in the input array.
2
Create a count[k+1] array. Increment count[arr[i]] for each element.
3
Compute prefix sums: count[i] += count[i-1]. Now count[v] = how many elements are ≤ v.
4
Walk the input backwards, place each element at position count[arr[i]]-1 in the output, then decrement count[arr[i]].

counting_sort.c

void countingSort(int arr[], int n) {
    int max = arr[0];
    for (int i=1; i<n; i++) if (arr[i] > max) max = arr[i];

    int count[max+1];
    for (int i=0; i<=max; i++) count[i] = 0;

    for (int i=0; i<n; i++) count[arr[i]]++;          /* count each value */
    for (int i=1; i<=max; i++) count[i] += count[i-1]; /* prefix sums */

    int out[n];
    for (int i=n-1; i>=0; i--)      /* place stably, backwards */
        out[--count[arr[i]]] = arr[i];

    for (int i=0; i<n; i++) arr[i] = out[i];
}

Case	Time	Explanation
All cases	O(n + k)	n = number of elements, k = value range (max value)
Space	O(n + k)	count array of size k, output array of size n

When to use: Integers (or values mappable to integers) with a small known range. Sorting exam scores (0–100), ages (0–120), or characters (0–255) — Counting Sort is unbeatable. Avoid when k >> n (e.g. sorting 10 numbers with values up to 1,000,000 wastes a million cells). Foundation of Radix Sort.

algorithm 7

🌳 Heap Sort

Build a max-heap, repeatedly extract the maximum to sort in place

O(n log n)

Heap Sort uses a data structure called a max-heap — a binary tree where every parent is larger than its children. The root of a max-heap is always the maximum element. Heap Sort first builds a max-heap from the array, then repeatedly extracts the root (the maximum) and places it at the end of the array. After each extraction, it restores the heap property by "heapifying" downward. No extra memory needed — it sorts in-place.

1
Build max-heap: Call heapify on every non-leaf node from the bottom up. Array is now a valid max-heap.
2
The root arr[0] is the maximum. Swap it with the last unsorted element arr[n-1]. That element is now in its final sorted position.
3
Reduce heap size by 1. Call heapify on the root to restore the heap property.
4
Repeat steps 2–3 until heap size = 1. Array is fully sorted.

heap_sort.c

/* Restore max-heap property at node i, heap size = n */
void heapify(int arr[], int n, int i) {
    int largest = i;         /* assume root is largest */
    int l = 2*i + 1;         /* left child  */
    int r = 2*i + 2;         /* right child */

    if (l < n && arr[l] > arr[largest]) largest = l;
    if (r < n && arr[r] > arr[largest]) largest = r;

    if (largest != i) {       /* root wasn't largest — swap and recurse */
        int tmp = arr[i]; arr[i] = arr[largest]; arr[largest] = tmp;
        heapify(arr, n, largest);
    }
}

void heapSort(int arr[], int n) {
    /* Build max-heap (start from last non-leaf) */
    for (int i = n/2-1; i >= 0; i--)
        heapify(arr, n, i);

    /* Extract max one by one */
    for (int i = n-1; i > 0; i--) {
        int tmp = arr[0]; arr[0] = arr[i]; arr[i] = tmp;  /* root to end */
        heapify(arr, i, 0);   /* restore heap on reduced array */
    }
}

Case	Time	Explanation
Best	O(n log n)	Build heap O(n) + n extractions each O(log n)
Average	O(n log n)	Always the same structure regardless of input
Worst	O(n log n)	Guaranteed — no bad pivot or degenerate case
Space	O(1)	In-place — no extra arrays, only stack for recursion

Heap Sort's unique advantage: O(n log n) guaranteed and O(1) extra space. Neither Merge Sort (O(n) space) nor Quick Sort (O(n²) worst case) can match both simultaneously. Used in embedded systems and real-time software where memory is tight and worst-case guarantees are required.

summary

📋

Complete Comparison — All 7 Algorithms

Time, space, stability, adaptivity — when to use each one

Summary

No single sorting algorithm wins on every metric. The right choice depends on your input size, data range, whether the data is nearly sorted, and your memory constraints. This table gives the full picture at a glance.

algorithm comparison table

Algorithm	Best	Average	Worst	Space	Stable?	Use when...
Bubble Sort	O(n)	O(n²)	O(n²)	O(1)	✓ Yes	Learning / nearly sorted / tiny array
Selection Sort	O(n²)	O(n²)	O(n²)	O(1)	✗ No	Minimum swaps needed / small array
Insertion Sort	O(n)	O(n²)	O(n²)	O(1)	✓ Yes	Nearly sorted / streaming / n < 50
Merge Sort	O(n log n)	O(n log n)	O(n log n)	O(n)	✓ Yes	Guaranteed performance / linked lists / stability required
Quick Sort	O(n log n)	O(n log n)	O(n²)	O(log n)	✗ No	General-purpose / large arrays / cache-friendly
Counting Sort	O(n+k)	O(n+k)	O(n+k)	O(n+k)	✓ Yes	Integer keys / small value range k
Heap Sort	O(n log n)	O(n log n)	O(n log n)	O(1)	✗ No	Guaranteed O(n log n) with O(1) space

Decision guide in plain English:

➤ n < 20? Insertion Sort. Dead simple, no overhead.
➤ Nearly sorted? Insertion Sort (O(n) best case).
➤ General purpose? Quick Sort (fastest average, cache-friendly).
➤ Need stability? Merge Sort (equal elements keep original order).
➤ Memory limited? Heap Sort (O(n log n) guaranteed, O(1) space).
➤ Integers, small range? Counting Sort (beats all comparison sorts).
➤ Linked list? Merge Sort (no random access needed, no extra memory).
➤ Standard library? Use qsort() in C — well-tested, fast, portable.

Real-world sorting is hybrid. Python's timsort, Java's Arrays.sort, and C++'s std::sort all combine multiple algorithms: Insertion Sort for small subarrays, Merge Sort or Quick Sort for larger ones, with special handling for nearly-sorted runs. No single algorithm is best for all cases.

checklist

Bubble Sort — repeated adjacent swaps. Largest bubbles to end each pass. O(n) best with early exit. O(n²) worst.
Selection Sort — find minimum, swap to front. Exactly n-1 swaps. O(n²) always — no best case.
Insertion Sort — pick key, slide it left into sorted position. O(n) on nearly-sorted. Best of the O(n²) sorts.
Merge Sort — divide in half, sort each, merge. O(n log n) guaranteed. Stable. Costs O(n) extra space.
Quick Sort — pick pivot, partition, recurse. O(n log n) average. O(n²) worst with bad pivot. Fastest in practice.
Counting Sort — count occurrences, compute positions, place. O(n+k). No comparisons. Only works on integers with small range.
Heap Sort — build max-heap, extract root repeatedly. O(n log n) guaranteed AND O(1) space. Best of both worlds.
Stability — Bubble, Insertion, Merge, Counting are stable. Selection, Quick, Heap are not.

Sorting Algorithms —Explained Simply

Sorting Algorithms —
Explained Simply