Counting Sort & Heap Sort | Ananta Code Academy

🔢 Counting Sort — Sort Without Comparisons

Count frequencies, prefix-sum to find positions, place each element exactly — O(n + k)

O(n + k)

Counting Sort does not compare elements — it counts them. For an array whose values range from 0 to k, it creates a count array of size k + 1 and increments count[val] for every element. A prefix-sum pass then converts each count into the last valid output index for that value. Finally, elements are placed into the output array in reverse order — ensuring the sort is stable (equal elements keep their original relative order). Time: O(n + k). Space: O(n + k). Best when k is small relative to n.

counting_sort.c

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

void printArr(const char *label, int *a, int n) {
    printf("%-16s: ", label);
    for (int i = 0; i < n; i++) printf("%3d", a[i]);
    printf("\n");
}

void countingSort(int *arr, int n) {
    /* Step 1: find the range */
    int max = arr[0];
    for (int i = 1; i < n; i++)
        if (arr[i] > max) max = arr[i];

    /* Step 2: allocate and zero the count array */
    int *cnt = (int*)calloc(max + 1, sizeof(int));
    int *out = (int*)malloc(n * sizeof(int));

    /* Step 3: count occurrences */
    for (int i = 0; i < n; i++) cnt[arr[i]]++;
    printf("\n--- Count array (value : frequency) ---\n");
    for (int v = 0; v <= max; v++)
        if (cnt[v]) printf("  value %d : %d time(s)\n", v, cnt[v]);

    /* Step 4: prefix-sum — cnt[v] now = last output index + 1 */
    for (int v = 1; v <= max; v++) cnt[v] += cnt[v - 1];
    printf("\n--- Prefix-sum array (value : position) ---\n");
    for (int v = 0; v <= max; v++)
        if (cnt[v]) printf("  value %d : goes up to index %d\n", v, cnt[v]-1);

    /* Step 5: place elements in reverse — keeps sort STABLE */
    for (int i = n - 1; i >= 0; i--) {
        out[--cnt[arr[i]]] = arr[i];
    }

    /* Step 6: copy result back */
    memcpy(arr, out, n * sizeof(int));
    free(cnt); free(out);
}

int main() {
    int arr[] = { 4, 2, 9, 3, 2, 7, 1, 5, 4, 3, 9, 1 };
    int  n   = sizeof(arr) / sizeof(arr[0]);

    printf("=== Counting Sort ===\n");
    printArr("Input", arr, n);

    countingSort(arr, n);

    printf("\n");
    printArr("Sorted", arr, n);
    return 0;
}

output

=== Counting Sort ===
Input           :   4  2  9  3  2  7  1  5  4  3  9  1

--- Count array (value : frequency) ---
  value 1 : 2 time(s)
  value 2 : 2 time(s)
  value 3 : 2 time(s)
  value 4 : 2 time(s)
  value 5 : 1 time(s)
  value 7 : 1 time(s)
  value 9 : 2 time(s)

--- Prefix-sum array (value : position) ---
  value 1 : goes up to index 1
  value 2 : goes up to index 3
  value 3 : goes up to index 5
  value 4 : goes up to index 7
  value 5 : goes up to index 8
  value 7 : goes up to index 9
  value 9 : goes up to index 11

Sorted          :   1  1  2  2  3  3  4  4  5  7  9  9

three-phase trace — input → count → prefix-sum → output

Input arr

← n elements

count[ ]

← index = value

prefix sum

← cumulative

Output

← sorted

When to use Counting Sort: when all values are non-negative integers and the range k is small — e.g. exam marks 0–100, ASCII character frequencies, age groups. It degrades to O(n·k) memory waste if values are sparse or huge (like sorting 10 numbers in range 0–1 000 000). For such cases, use Radix Sort instead.

Stability matters: iterating the input array in reverse during placement (Step 5) guarantees that equal elements appear in the output in the same relative order they appeared in the input. This makes Counting Sort a stable sort — a required property when it is used as a subroutine inside Radix Sort.

example 2

🌳 Heap Sort — Sort Using a Max-Heap

Build a max-heap in-place, repeatedly extract the maximum — O(n log n) guaranteed

O(n log n)

Heap Sort uses the max-heap property: the parent node is always larger than its children. The algorithm has two phases. Phase 1 — Build heap: call heapify bottom-up on every non-leaf node, turning the array into a valid max-heap in O(n). Phase 2 — Extract: swap the root (maximum) with the last element, reduce the heap size by 1, and heapify the new root down. Repeat n-1 times. Each extraction is O(log n), so total is O(n log n) in all cases. Space: O(1) — entirely in-place, no extra array needed.

heap_sort.c

#include <stdio.h>

void printArr(const char *label, int *a, int n) {
    printf("%-16s: ", label);
    for (int i = 0; i < n; i++) printf("%4d", a[i]);
    printf("\n");
}

/* Sift element at index i down in a heap of size n */
void heapify(int *arr, int n, int i) {
    int largest = i;             /* assume root is largest */
    int left    = 2 * i + 1;    /* left  child index     */
    int right   = 2 * i + 2;    /* right child index     */

    if (left  < n && arr[left]  > arr[largest]) largest = left;
    if (right < n && arr[right] > arr[largest]) largest = right;

    if (largest != i) {          /* swap and recurse down */
        int tmp = arr[i];
        arr[i] = arr[largest];
        arr[largest] = tmp;
        heapify(arr, n, largest);
    }
}

void heapSort(int *arr, int n) {
    /* Phase 1: build max-heap bottom-up — O(n) */
    printf("\n--- Phase 1: Build Max-Heap ---\n");
    for (int i = n / 2 - 1; i >= 0; i--)
        heapify(arr, n, i);
    printArr("Max-heap", arr, n);

    /* Phase 2: extract maximum one by one — O(n log n) */
    printf(\n"--- Phase 2: Extract Max ---\n");
    for (int end = n - 1; end > 0; end--) {
        /* Move current root (max) to sorted end */
        int tmp = arr[0];
        arr[0]   = arr[end];
        arr[end] = tmp;
        printf("  Extracted %2d  -> arr[%d]  heap: ", tmp, end);
        for (int k = 0; k < end; k++) printf("%d ", arr[k]);
        printf("\n");
        /* Restore heap property for remaining n-1 elements */
        heapify(arr, end, 0);
    }
}

int main() {
    int arr[] = { 12, 3, 7, 18, 5, 9, 1, 15, 6, 11 };
    int  n   = sizeof(arr) / sizeof(arr[0]);

    printf("=== Heap Sort ===\n");
    printArr("Input", arr, n);

    heapSort(arr, n);

    printf("\n");
    printArr("Sorted", arr, n);
    return 0;
}

output

=== Heap Sort ===
Input           :   12   3   7  18   5   9   1  15   6  11

--- Phase 1: Build Max-Heap ---
Max-heap        :   18  15   9  12  11   7   1   3   6   5

--- Phase 2: Extract Max ---
  Extracted 18  -> arr[9]  heap: 15 12 9 6 11 7 1 3 5
  Extracted 15  -> arr[8]  heap: 12 11 9 6 5 7 1 3
  Extracted 12  -> arr[7]  heap: 11 6 9 3 5 7 1
  Extracted 11  -> arr[6]  heap: 9 6 7 3 5 1
  Extracted  9  -> arr[5]  heap: 7 6 1 3 5
  Extracted  7  -> arr[4]  heap: 6 5 1 3
  Extracted  6  -> arr[3]  heap: 5 3 1
  Extracted  5  -> arr[2]  heap: 3 1
  Extracted  3  -> arr[1]  heap: 1

Sorted          :    1   3   5   6   7   9  11  12  15  18

max-heap as an array — parent / child index relationships

Array index

← index i

Max-heap

← root = max

Left child

2i + 1

← e.g. i=0 → left=1 (value 15)

Right child

2i + 2

← e.g. i=0 → right=2 (value 9)

Parent

(i - 1) / 2

← e.g. i=3 → parent=1 (value 15)

Heap Sort is O(n log n) in all cases — best, average, and worst. Unlike Quick Sort it never degrades to O(n²). Unlike Merge Sort it uses O(1) extra space. The trade-off: it is not stable (equal elements may change order) and has poor cache performance because heapify accesses distant array positions. Use it when guaranteed worst-case time and O(1) space are both required.

Only non-leaf nodes need heapifying. Leaves (indices n/2 to n-1) are already trivially valid heaps of size 1, so the build-heap loop starts at index n/2 - 1 and works backwards to 0. This is why building the heap is O(n), not O(n log n) — a surprising but provable result.

checklist

Counting Sort — count frequencies in cnt[val], prefix-sum to find positions, place in reverse for stability. Time O(n + k), Space O(n + k). Best when k is small.
Heap Sort — Phase 1: build max-heap in O(n) bottom-up starting at n/2-1. Phase 2: swap root (max) with last, shrink heap, heapify root. Guaranteed O(n log n), O(1) space, not stable.

Counting Sort &Heap Sort in C

Counting Sort &
Heap Sort in C