Sorting Algorithms — Visualized

Sorting — Why Seven Different Algorithms?

Every sorting algorithm makes the same promise (rearrange elements into order) but trades off differently on speed, memory, stability, and behavior on nearly-sorted data.

Key Vocabulary TERMINOLOGY

• In-place — uses O(1) extra memory beyond the input array.
• Stable — equal elements keep their original relative order.
• Comparison-based — decides order only by comparing pairs of elements (lower bound Ω(n log n)); Radix sort is not comparison-based and can beat that bound.
• Adaptive — runs faster on already/partially-sorted input.

Complexity & Property Comparison CHEAT SHEET

Algorithm	Best	Average	Worst	Space	Stable?	In-place?
Selection Sort	n²	n²	n²	1	✗	✓
Bubble Sort	n	n²	n²	1	✓	✓
Insertion Sort	n	n²	n²	1	✓	✓
Merge Sort	n log n	n log n	n log n	n	✓	✗
Heap Sort	n log n	n log n	n log n	1	✗	✓
Quick Sort	n log n	n log n	n²	log n	✗	✓
Radix Sort	n·k	n·k	n·k	n+k	✓	✗

📌 k in Radix Sort's complexity is the number of digits in the largest number — since k is typically small and fixed, Radix Sort achieves effectively linear time, beating the Ω(n log n) lower bound that applies only to comparison-based sorts.

How to Use This Module GUIDE

Read each algorithm's tab for the concept, pseudocode, and complexity — then jump to the Animated Visualizer tab, pick that algorithm from the dropdown, and watch it sort a live bar chart with full play/pause/step/stop control and an adjustable speed slider.

Selection Sort

Repeatedly find the minimum of the unsorted remainder and swap it into place — the simplest possible sorting strategy.

Idea CONCEPT

Split the array into a sorted prefix (initially empty) and an unsorted suffix. On each pass, scan the entire unsorted suffix to find its minimum element, then swap it into the first position of that suffix — extending the sorted prefix by one.

📌 Selection Sort always makes exactly n−1 swaps in the worst case — fewer than Bubble Sort — but it never stops early even on a sorted array, since it must scan for the minimum every single pass.

Pseudocode ALGORITHM

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

Time: O(n²) always Space: O(1) Stable: No In-place: Yes

Bubble Sort

Repeatedly swap adjacent out-of-order elements — each pass "bubbles" the largest remaining value to its final position at the end.

Idea CONCEPT

Scan the array left to right, comparing each adjacent pair. If they're out of order, swap them. After one full pass, the largest element is guaranteed to be at the end. Repeat for a shrinking unsorted prefix. A pass with zero swaps means the array is already sorted — allowing early exit.

📌 This early-exit optimization makes Bubble Sort adaptive: on an already-sorted array it runs in O(n) — a single pass that finds no swaps needed.

Pseudocode ALGORITHM

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 not swapped:
        break                     // already sorted

Time: O(n) best (sorted), O(n²) avg/worst Space: O(1) Stable: Yes In-place: Yes

Insertion Sort

Build the sorted array one element at a time, exactly the way most people sort a hand of playing cards.

Idea CONCEPT

Treat the first element as a trivially-sorted prefix of length 1. For each next element (the "key"), shift all larger elements in the sorted prefix one position to the right, then insert the key into the gap that opens up. Repeat until the whole array is processed.

📌 Insertion Sort is highly efficient on nearly-sorted data — each key typically shifts only a few (or zero) positions, giving close to O(n) performance in practice, which is why it's often used as the base case inside hybrid sorts like Timsort.

Pseudocode ALGORITHM

for i = 1 to n-1:
    key = a[i]
    j = i - 1
    while j >= 0 and a[j] > key:
        a[j+1] = a[j]          // shift right
        j = j - 1
    a[j+1] = key                 // insert key into the gap

Time: O(n) best (sorted), O(n²) avg/worst Space: O(1) Stable: Yes In-place: Yes

Merge Sort

Divide the array in half recursively until pieces of size 1 remain, then merge sorted pieces back together — the classic divide-and-conquer sort.

Idea DIVIDE & CONQUER

1. Divide: split the array into two halves.
2. Conquer: recursively sort each half.
3. Combine: merge the two sorted halves into one sorted array by repeatedly comparing their front elements.

DIAGRAM — RECURSIVE SPLIT & MERGE

Pseudocode ALGORITHM

function mergeSort(a, lo, hi):
    if lo >= hi: return
    mid = (lo + hi) / 2
    mergeSort(a, lo, mid)
    mergeSort(a, mid+1, hi)
    merge(a, lo, mid, hi)

function merge(a, lo, mid, hi):
    left = a[lo..mid], right = a[mid+1..hi]
    i = j = 0, k = lo
    while i < left.length and j < right.length:
        if left[i] <= right[j]: a[k++] = left[i++]
        else:                  a[k++] = right[j++]
    copy any remaining elements of left / right into a

Time: O(n log n) always Space: O(n) extra Stable: Yes In-place: No

Heap Sort

Build a max-heap so the largest element sits at the root, then repeatedly move the root to the end of the array and re-heapify.

Idea CONCEPT

1. Build a max-heap from the array (every parent ≥ its children) — done in O(n) via bottom-up heapify.
2. Repeatedly: swap the root (maximum) with the last unsorted element, shrink the heap by one, and "sift down" the new root to restore the heap property.
3. After n such extractions, the array is fully sorted in place.

DIAGRAM — MAX-HEAP AS A TREE (ARRAY-BACKED)

Pseudocode ALGORITHM

function heapify(a, n, i):    // sift a[i] down in a heap of size n
    largest = i, l = 2i+1, r = 2i+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)

function heapSort(a):
    n = a.length
    for i = n/2 - 1 downto 0: heapify(a, n, i)   // build max-heap
    for i = n-1 downto 1:
        swap(a[0], a[i])                   // move max to the end
        heapify(a, i, 0)                  // restore heap on shrunk range

Time: O(n log n) always Space: O(1) Stable: No In-place: Yes

Quick Sort

Pick a pivot, partition the array around it, then recursively sort each side — usually the fastest general-purpose comparison sort in practice.

Idea — Lomuto Partition CONCEPT

1. Choose a pivot (commonly the last element).
2. Partition: rearrange the array so everything less than the pivot ends up left of it, everything greater ends up right of it — the pivot lands in its final sorted position.
3. Recursively quick-sort the left and right sub-arrays.

DIAGRAM — PARTITION AROUND A PIVOT

Pseudocode ALGORITHM

function partition(a, lo, hi):
    pivot = a[hi]
    i = lo - 1
    for j = lo to hi-1:
        if a[j] < pivot:
            i++
            swap(a[i], a[j])
    swap(a[i+1], a[hi])
    return i + 1                 // pivot's final index

function quickSort(a, lo, hi):
    if lo < hi:
        p = partition(a, lo, hi)
        quickSort(a, lo, p-1)
        quickSort(a, p+1, hi)

Time: O(n log n) avg, O(n²) worst (already-sorted + bad pivot) Space: O(log n) Stable: No In-place: Yes

⚠️ Choosing the pivot poorly (e.g. always the first/last element of an already-sorted array) degrades Quick Sort to O(n²). Randomized or median-of-three pivot selection avoids this in practice.

Radix Sort

A non-comparison sort: process numbers digit by digit, from least-significant to most-significant, using a stable counting sort at each digit position.

Idea CONCEPT

Sort the numbers repeatedly by each digit, starting from the ones place and moving toward higher place values. Because each pass uses a stable sort (Counting Sort), the relative order established by earlier (less significant) digit passes is preserved — so by the time the most significant digit is processed, the whole array is correctly ordered.

DIAGRAM — SORTING [170, 45, 75, 90, 802, 24, 2, 66] BY DIGIT

Pseudocode ALGORITHM

function countingSortByDigit(a, exp):  // exp = 1, 10, 100, ...
    output = array of size n
    count = array of size 10, initialized to 0
    for i = 0 to n-1:
        d = (a[i] / exp) % 10
        count[d]++
    for d = 1 to 9: count[d] += count[d-1]     // prefix sums
    for i = n-1 downto 0:                    // iterate backward for stability
        d = (a[i] / exp) % 10
        output[count[d]-1] = a[i]
        count[d]--
    a = output

function radixSort(a):
    maxVal = max(a)
    for exp = 1; maxVal/exp > 0; exp *= 10:
        countingSortByDigit(a, exp)

Time: O(n·k) where k = number of digits Space: O(n+k) Stable: Yes In-place: No

Animated Visualizer — Watch Every Algorithm Sort

Pick an algorithm, generate a random (or custom) array, and watch it sort bar by bar — with color-coded comparisons, swaps, and pivots, full play/pause/step/stop control, and an adjustable speed slider.

Setup CONFIGURE

Algorithm: Array size: 25

Custom array (comma-separated, optional):

📌 Radix Sort requires non-negative integers — Randomize automatically generates suitable values for the selected algorithm.

Playback LIVE

Speed: 40ms / step

Comparisons: 0 Swaps / Writes: 0 Step: 0 / 0 Complexity: O(n²)

ARRAY — default · comparing · swapping · pivot · sorted

C Implementations

Complete, compilable C functions for all seven sorting algorithms.

selection_sort.c O(n²)

void selectionSort(int a[], int n) {
    for (int i = 0; i < n - 1; i++) {
        int minIdx = i;
        for (int j = i + 1; j < n; j++)
            if (a[j] < a[minIdx]) minIdx = j;
        if (minIdx != i) {
            int tmp = a[i]; a[i] = a[minIdx]; a[minIdx] = tmp;
        }
    }
}

bubble_sort.c O(n²) / O(n) adaptive

void bubbleSort(int a[], int n) {
    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]) {
                int tmp = a[j]; a[j] = a[j+1]; a[j+1] = tmp;
                swapped = 1;
            }
        }
        if (!swapped) break;
    }
}

insertion_sort.c O(n²) / O(n) adaptive

void insertionSort(int a[], int n) {
    for (int i = 1; i < n; i++) {
        int key = a[i], j = i - 1;
        while (j >= 0 && a[j] > key) {
            a[j + 1] = a[j];
            j--;
        }
        a[j + 1] = key;
    }
}

merge_sort.c O(n log n)

void merge(int a[], 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] = a[lo + i];
    for (int j = 0; j < n2; j++) R[j] = a[mid + 1 + j];
    int i = 0, j = 0, k = lo;
    while (i < n1 && j < n2)
        a[k++] = (L[i] <= R[j]) ? L[i++] : R[j++];
    while (i < n1) a[k++] = L[i++];
    while (j < n2) a[k++] = R[j++];
}

void mergeSort(int a[], int lo, int hi) {
    if (lo >= hi) return;
    int mid = lo + (hi - lo) / 2;
    mergeSort(a, lo, mid);
    mergeSort(a, mid + 1, hi);
    merge(a, lo, mid, hi);
}

heap_sort.c O(n log n)

void heapify(int a[], int n, int i) {
    int largest = i, l = 2*i + 1, r = 2*i + 2;
    if (l < n && a[l] > a[largest]) largest = l;
    if (r < n && a[r] > a[largest]) largest = r;
    if (largest != i) {
        int tmp = a[i]; a[i] = a[largest]; a[largest] = tmp;
        heapify(a, n, largest);
    }
}

void heapSort(int a[], int n) {
    for (int i = n/2 - 1; i >= 0; i--) heapify(a, n, i);
    for (int i = n - 1; i > 0; i--) {
        int tmp = a[0]; a[0] = a[i]; a[i] = tmp;
        heapify(a, i, 0);
    }
}

quick_sort.c O(n log n) avg, O(n²) worst

int partition(int a[], int lo, int hi) {
    int pivot = a[hi], i = lo - 1;
    for (int j = lo; j < hi; j++) {
        if (a[j] < pivot) {
            i++;
            int tmp = a[i]; a[i] = a[j]; a[j] = tmp;
        }
    }
    int tmp = a[i+1]; a[i+1] = a[hi]; a[hi] = tmp;
    return i + 1;
}

void quickSort(int a[], int lo, int hi) {
    if (lo < hi) {
        int p = partition(a, lo, hi);
        quickSort(a, lo, p - 1);
        quickSort(a, p + 1, hi);
    }
}

radix_sort.c O(n·k)

int getMax(int a[], int n) {
    int mx = a[0];
    for (int i = 1; i < n; i++) if (a[i] > mx) mx = a[i];
    return mx;
}

void countingSortByDigit(int a[], int n, int exp) {
    int output[n], count[10] = {0};
    for (int i = 0; i < n; i++) count[(a[i]/exp) % 10]++;
    for (int d = 1; d < 10; d++) count[d] += count[d-1];
    for (int i = n - 1; i >= 0; i--) {
        int d = (a[i]/exp) % 10;
        output[count[d]-1] = a[i];
        count[d]--;
    }
    for (int i = 0; i < n; i++) a[i] = output[i];
}

void radixSort(int a[], int n) {
    int mx = getMax(a, n);
    for (int exp = 1; mx/exp > 0; exp *= 10)
        countingSortByDigit(a, n, exp);
}

📌 All seven functions operate on a plain C int a[] array — swap any into a common driver main() that fills the array, calls one sort, and prints the result.

Sorting AlgorithmsSelection, Bubble, Insertion, Merge, Heap, Quick & Radix

Sorting Algorithms
Selection, Bubble, Insertion, Merge, Heap, Quick & Radix