Master the Top 10 Sorting Algorithms in Java: From Bubble to Radix

Introduction

As a programmer, mastering the ten classic sorting algorithms is essential. This article reviews bubble sort, quick sort, insertion sort, shell sort, selection sort, heap sort, merge sort, bucket sort, counting sort, and radix sort, explaining their principles, time/space complexities, and stability.

Classification

Sorting algorithms are divided into comparison‑based and non‑comparison‑based families. The non‑comparison group includes bucket, counting, and radix sort; the comparison group is further split into exchange, insertion, selection, and merge‑based methods.

Exchange‑based

Bubble Sort

Bubble sort repeatedly swaps adjacent elements, moving the largest (or smallest) element to its final position each pass. It is stable with O(n²) time.

Example array:

2 5 3 1 4

public void maopaosort(int[] a) {
    for (int i = a.length - 1; i >= 0; i--) {
        for (int j = 0; j < i; j++) {
            if (a[j] > a[j + 1]) {
                int tmp = a[j];
                a[j] = a[j + 1];
                a[j + 1] = tmp;
            }
        }
    }
}

Quick Sort

Quick sort uses a divide‑and‑conquer strategy with recursion. It is unstable, average O(n log n) time, worst O(n²).

public void quicksort(int[] a, int left, int right) {
    int low = left, high = right;
    if (low > high) return;
    int pivot = a[low];
    while (low < high) {
        while (low < high && a[high] >= pivot) high--;
        a[low] = a[high];
        while (low < high && a[low] <= pivot) low++;
        a[high] = a[low];
    }
    a[low] = pivot;
    quicksort(a, left, low - 1);
    quicksort(a, low + 1, right);
}

Insertion‑based

Insertion Sort

Insertion sort builds a sorted portion by inserting each element into its proper place. Time complexity O(n²); stability is guaranteed.

public void insertsort(int[] a) {
    for (int i = 1; i < a.length; 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;
    }
}

Shell Sort

Shell sort improves insertion sort by sorting elements spaced by a decreasing gap, reducing the number of movements.

public void shellsort(int[] a) {
    int gap = a.length;
    for (; gap >= 1; gap /= 2) {
        for (int i = gap; i < a.length; i++) {
            int temp = a[i];
            int j = i - gap;
            while (j >= 0 && a[j] > temp) {
                a[j + gap] = a[j];
                j -= gap;
            }
            a[j + gap] = temp;
        }
    }
}

Selection‑based

Selection Sort

Selection sort repeatedly selects the minimum element and swaps it to the front. It is unstable with O(n²) time.

public void selectSort(int[] arr) {
    for (int i = 0; i < arr.length - 1; i++) {
        int min = i;
        for (int j = i + 1; j < arr.length; j++) {
            if (arr[j] < arr[min]) min = j;
        }
        if (min != i) swap(arr, i, min);
    }
}
private void swap(int[] arr, int i, int j) {
    int tmp = arr[i];
    arr[i] = arr[j];
    arr[j] = tmp;
}

Heap Sort

Heap sort first builds a binary heap (max‑heap for ascending order) and then repeatedly extracts the root, restoring the heap each time. Time O(n log n), space O(1), unstable.

static void heapSort(int[] arr) {
    // Build heap (implementation omitted for brevity)
    // Repeatedly extract max and rebuild heap
}

Merge‑based

Merge Sort

Merge sort recursively splits the array into halves, sorts each half, and merges them. It is stable with O(n log n) time and O(n) extra space.

private void mergesort(int[] a, int left, int right) {
    if (left < right) {
        int mid = (left + right) / 2;
        mergesort(a, left, mid);
        mergesort(a, mid + 1, right);
        merge(a, left, mid, right);
    }
}

Non‑comparison‑based

Bucket Sort

Bucket sort distributes elements into a number of buckets, sorts each bucket (often with another algorithm), and concatenates the results. Best case linear time when data is uniformly distributed.

public static void bucketSort(int[] a) {
    // Bucket creation, distribution, sorting, and collection (implementation omitted)
}

Counting Sort

Counting sort counts occurrences of each distinct value, then computes positions. It runs in O(n + k) time where k is the range of input.

public static void countSort(int[] a) {
    int min = Integer.MAX_VALUE, max = Integer.MIN_VALUE;
    for (int v : a) {
        if (v < min) min = v;
        if (v > max) max = v;
    }
    int[] count = new int[max - min + 1];
    for (int v : a) count[v - min]++;
    int idx = 0;
    for (int i = 0; i < count.length; i++) {
        while (count[i]-- > 0) a[idx++] = i + min;
    }
}

Radix Sort

Radix sort processes digits from least‑significant to most‑significant using counting sort as a sub‑routine. It achieves O(n k) time for n numbers with k digit positions.

static void radixSort(int[] arr) {
    // Determine max value
    int max = 0;
    for (int v : arr) if (v > max) max = v;
    int exp = 1;
    while (max / exp > 0) {
        // Distribute based on current digit
        // Collect back into arr (implementation omitted)
        exp *= 10;
    }
}