Master the Top 10 Classic Sorting Algorithms with Code and Visualizations

Complexity Overview

The ten classic sorting algorithms differ in average and worst‑case time complexity, auxiliary space usage, and stability:

Bubble, Selection, Insertion: O(n²) time, O(1) extra space, stable except Selection (unstable for arrays).

Quick, Heap, Merge, Shell: O(n·log₂n) average time; Quick worst‑case O(n²), Heap and Merge worst‑case O(n·log₂n), Shell worst‑case O(n²). Space: Quick O(log₂n) recursion stack, Heap O(1), Merge O(n), Shell O(1). Stability: Merge stable; others unstable.

Counting, Bucket, Radix: Linear‑time variants. Counting O(n+m) time and space (m = range of keys), stable. Bucket O(n) average time, O(m) space, stable. Radix O(k·n) time (k = number of digits), stable.

1. Bubble Sort

Idea: Repeatedly compare adjacent elements and swap them if they are out of order, causing the largest unsorted element to “bubble” to the end of the array after each pass.

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

2. Selection Sort

Idea: For each position, find the minimum element in the remaining unsorted portion and swap it into the current position.

function selectionSort(arr) {
    var len = arr.length;
    for (var i = 0; i < len - 1; i++) {
        var minIdx = i;
        for (var j = i + 1; j < len; j++) {
            if (arr[j] < arr[minIdx]) minIdx = j;
        }
        var tmp = arr[i];
        arr[i] = arr[minIdx];
        arr[minIdx] = tmp;
    }
    return arr;
}

3. Insertion Sort

Idea: Build the sorted portion of the array one element at a time by inserting each new element into its correct position among the already sorted elements.

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

4. Quick Sort

Idea: Choose a pivot (commonly the first element), partition the array so that elements smaller than the pivot are on the left and larger on the right, then recursively sort the two partitions.

void quickSort(vector<int>& v, int low, int high) {
    if (low >= high) return;
    int i = low, j = high;
    int pivot = v[low];
    while (i < j) {
        while (i < j && v[j] >= pivot) --j;
        if (i < j) v[i++] = v[j];
        while (i < j && v[i] <= pivot) ++i;
        if (i < j) v[j--] = v[i];
    }
    v[i] = pivot;
    quickSort(v, low, i - 1);
    quickSort(v, i + 1, high);
}

5. Heap Sort

Idea: Build a max‑heap from the input array, repeatedly swap the root (maximum) with the last element of the heap, shrink the heap size, and restore the heap property.

#include <iostream>
#include <algorithm>
using namespace std;

void maxHeapify(int arr[], int start, int end) {
    int dad = start;
    int son = dad * 2 + 1;
    while (son <= end) {
        if (son + 1 <= end && arr[son] < arr[son + 1]) ++son;
        if (arr[dad] >= arr[son]) break;
        swap(arr[dad], arr[son]);
        dad = son;
        son = dad * 2 + 1;
    }
}

void heapSort(int arr[], int len) {
    for (int i = len / 2 - 1; i >= 0; --i) maxHeapify(arr, i, len - 1);
    for (int i = len - 1; i > 0; --i) {
        swap(arr[0], arr[i]);
        maxHeapify(arr, 0, i - 1);
    }
}

6. Merge Sort

Idea: Recursively split the array into halves, sort each half, then merge the two sorted halves (divide‑and‑conquer).

void merge(int *src, int *dest, int left, int mid, int right) {
    int i = left, j = mid + 1, k = left;
    while (i <= mid && j <= right) {
        dest[k++] = (src[i] <= src[j]) ? src[i++] : src[j++];
    }
    while (i <= mid) dest[k++] = src[i++];
    while (j <= right) dest[k++] = src[j++];
    for (int p = left; p <= right; ++p) src[p] = dest[p];
}

void mergeSort(int *arr, int *temp, int left, int right) {
    if (left >= right) return;
    int mid = (left + right) / 2;
    mergeSort(arr, temp, left, mid);
    mergeSort(arr, temp, mid + 1, right);
    merge(arr, temp, left, mid, right);
}

7. Shell Sort

Idea: Generalize insertion sort by sorting elements that are a certain gap apart; the gap sequence is gradually reduced until it becomes 1, at which point the algorithm finishes with a standard insertion sort.

template<typename T>
void shellSort(T a[], int n) {
    int gap = 1;
    while (gap < n / 3) gap = 3 * gap + 1; // 1, 4, 13, 40, ...
    while (gap >= 1) {
        for (int i = gap; i < n; ++i) {
            T temp = a[i];
            int j = i;
            while (j >= gap && a[j - gap] > temp) {
                a[j] = a[j - gap];
                j -= gap;
            }
            a[j] = temp;
        }
        gap /= 3;
    }
}

8. Counting Sort

Idea: Count the occurrences of each distinct integer key, compute prefix sums to determine the final positions, and place elements directly into the output array. Works when keys are integers in a known small range.

#include <vector>
#include <algorithm>
using namespace std;

void countingSort(const vector<int>& input, vector<int>& output) {
    if (input.empty()) return;
    int maxVal = *max_element(input.begin(), input.end());
    vector<int> count(maxVal + 1, 0);
    for (int v : input) ++count[v];
    for (size_t i = 1; i < count.size(); ++i) count[i] += count[i - 1];
    output.resize(input.size());
    for (int i = (int)input.size() - 1; i >= 0; --i) {
        output[--count[input[i]]] = input[i]; // stable placement
    }
}

9. Bucket Sort

Idea: Distribute elements into a number of buckets based on value range, sort each bucket (commonly with insertion sort), then concatenate the buckets.

function bucketSort(arr, bucketSize) {
    if (arr.length === 0) return [];
    var min = Math.min(...arr);
    var max = Math.max(...arr);
    var bucketCount = Math.floor((max - min) / bucketSize) + 1;
    var buckets = Array.from({length: bucketCount}, () => []);
    for (var i = 0; i < arr.length; i++) {
        var idx = Math.floor((arr[i] - min) / bucketSize);
        buckets[idx].push(arr[i]);
    }
    var sorted = [];
    for (var b = 0; b < buckets.length; b++) {
        insertionSort(buckets[b]); // assume insertionSort is defined
        sorted = sorted.concat(buckets[b]);
    }
    return sorted;
}

10. Radix Sort

Idea: Process integer keys digit by digit from least significant to most significant, using a stable counting sort at each digit to achieve linear‑time per digit.

int maxDigits(int data[], int n) {
    int maxVal = data[0];
    for (int i = 1; i < n; ++i) if (data[i] > maxVal) maxVal = data[i];
    int digits = 0;
    do { maxVal /= 10; ++digits; } while (maxVal > 0);
    return digits;
}

void radixSort(int data[], int n) {
    int d = maxDigits(data, n);
    int *tmp = new int[n];
    int count[10];
    int radix = 1;
    for (int i = 0; i < d; ++i) {
        fill(count, count + 10, 0);
        for (int j = 0; j < n; ++j) ++count[(data[j] / radix) % 10];
        for (int k = 1; k < 10; ++k) count[k] += count[k - 1];
        for (int j = n - 1; j >= 0; --j) {
            int idx = (data[j] / radix) % 10;
            tmp[--count[idx]] = data[j];
        }
        copy(tmp, tmp + n, data);
        radix *= 10;
    }
    delete[] tmp;
}

References

https://www.cnblogs.com/onepixel/p/7674659.html (animation source)

Electronic Engineering Collection