Comprehensive Guide to Ten Common Sorting Algorithms with Visual Explanations and Java Implementations

The article begins with an introduction that states the total length (14,237 characters) and the estimated reading time (47 minutes), encouraging readers to bookmark the page for a thorough study of sorting algorithms.

1. Bubble Sort

Bubble sort repeatedly steps through the list, compares adjacent elements, and swaps them if they are in the wrong order, moving the smallest (or largest) element to the end of the unsorted portion each pass.

Time complexity: O(n²); best case O(n) with early‑exit optimization.

public static void sort(int arr[]) {
    for (int i = 0; i < arr.length - 1; i++) {
        for (int j = 0; j < arr.length - 1 - i; j++) {
            int temp = 0;
            if (arr[j] < arr[j + 1]) {
                temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            }
        }
    }
}

Optimized Bubble Sort

An early‑exit flag stops the algorithm when a full pass makes no swaps.

public static void sort(int arr[]) {
    for (int i = 0; i < arr.length - 1; i++) {
        boolean isSort = true;
        for (int j = 0; j < arr.length - 1 - i; j++) {
            int temp = 0;
            if (arr[j] < arr[j + 1]) {
                temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
                isSort = false;
            }
        }
        if (isSort) {
            break;
        }
    }
}

2. Selection Sort

Selection sort repeatedly finds the minimum element from the unsorted portion and swaps it with the first unsorted element.

Time complexity: O(n²); space complexity: O(1).

public static void sort(int arr[]) {
    for (int i = 0; i < arr.length; i++) {
        int min = i; // index of the smallest element
        for (int j = i + 1; j < arr.length; j++) {
            if (arr[j] < arr[min]) {
                min = j;
            }
        }
        int temp = arr[i];
        arr[i] = arr[min];
        arr[min] = temp;
    }
}

3. Insertion Sort

Insertion sort builds the sorted array one element at a time by inserting each new element into its proper position among the already sorted elements.

Best case O(n), worst case O(n²).

public static void sort(int arr[]) {
    int n = arr.length;
    for (int i = 1; i < n; ++i) {
        int value = arr[i];
        int j = 0; // position to insert
        for (j = i - 1; j >= 0; j--) {
            if (arr[j] > value) {
                arr[j + 1] = arr[j];
            } else {
                break;
            }
        }
        arr[j + 1] = value;
    }
}

4. Shell Sort

Shell sort improves insertion sort by allowing exchanges of far‑apart elements using a decreasing gap sequence (commonly gap = gap*3 + 1).

Time complexity varies; typical implementations achieve O(n log² n).

public static void sort(int[] arr) {
    int length = arr.length;
    int gap = 1;
    while (gap < length) {
        gap = gap * 3 + 1;
    }
    while (gap > 0) {
        for (int i = gap; i < length; i++) {
            int tmp = arr[i];
            int j = i - gap;
            while (j >= 0 && arr[j] > tmp) {
                arr[j + gap] = arr[j];
                j -= gap;
            }
            arr[j + gap] = tmp;
        }
        gap = gap / 3;
    }
}

5. Merge Sort

Merge sort uses the divide‑and‑conquer strategy: recursively split the array into halves, sort each half, and merge them back together.

Time complexity: O(n log n); space complexity can be O(1) with in‑place merging as shown.

public static void sort(int[] arr) {
    int[] tempArr = new int[arr.length];
    sort(arr, tempArr, 0, arr.length - 1);
}
private static void sort(int[] arr, int[] tempArr, int start, int end) {
    if (end <= start) return;
    int mid = start + (end - start) / 2;
    sort(arr, tempArr, start, mid);
    sort(arr, tempArr, mid + 1, end);
    merge(arr, tempArr, start, mid, end);
}
private static void merge(int[] arr, int[] tempArr, int start, int mid, int end) {
    for (int s = start; s <= end; s++) tempArr[s] = arr[s];
    int left = start, right = mid + 1, k = start;
    while (k <= end) {
        if (left > mid) arr[k++] = tempArr[right++];
        else if (right > end) arr[k++] = tempArr[left++];
        else if (tempArr[right] < tempArr[left]) arr[k++] = tempArr[right++];
        else arr[k++] = tempArr[left++];
    }
}

6. Quick Sort

Quick sort also follows divide‑and‑conquer: choose a pivot, partition the array into elements less than and greater than the pivot, then recursively sort the partitions.

Average time O(n log n); worst case O(n²) when the pivot yields highly unbalanced partitions.

public static void sort(int[] arr) {
    sort(arr, 0, arr.length - 1);
}
private static void sort(int[] arr, int start, int end) {
    if (end <= start) return;
    int pivotIndex = partition(arr, start, end);
    sort(arr, start, pivotIndex - 1);
    sort(arr, pivotIndex + 1, end);
}
private static int partition(int[] arr, int start, int end) {
    int pivot = arr[start];
    int mark = start;
    for (int i = start + 1; i <= end; i++) {
        if (arr[i] < pivot) {
            mark++;
            int temp = arr[mark];
            arr[mark] = arr[i];
            arr[i] = temp;
        }
    }
    arr[start] = arr[mark];
    arr[mark] = pivot;
    return mark;
}

7. Heap Sort

Heap sort builds a max‑heap from the array, repeatedly extracts the maximum element (the heap root) and restores the heap property.

Time complexity: O(n log n); space complexity: O(1).

public static void sort(int[] arr) {
    int length = arr.length;
    buildHeap(arr, length);
    for (int i = length - 1; i > 0; i--) {
        int temp = arr[0];
        arr[0] = arr[i];
        arr[i] = temp;
        length--;
        sink(arr, 0, length);
    }
}
private static void buildHeap(int[] arr, int length) {
    for (int i = length / 2; i >= 0; i--) {
        sink(arr, i, length);
    }
}
private static void sink(int[] arr, int index, int length) {
    int left = 2 * index + 1;
    int right = 2 * index + 2;
    int largest = index;
    if (left < length && arr[left] > arr[largest]) largest = left;
    if (right < length && arr[right] > arr[largest]) largest = right;
    if (largest != index) {
        int temp = arr[index];
        arr[index] = arr[largest];
        arr[largest] = temp;
        sink(arr, largest, length);
    }
}

8. Counting Sort

Counting sort is a non‑comparison sort that counts the occurrences of each distinct value and then computes positions based on cumulative counts.

Ideal for non‑negative integers with a limited range; time O(n + k), space O(k).

public static void sort(int[] arr) {
    int max = arr[0];
    for (int i = 1; i < arr.length; i++) if (arr[i] > max) max = arr[i];
    int[] count = new int[max + 1];
    for (int i = 0; i < arr.length; i++) count[arr[i]]++;
    int index = 0;
    for (int i = 0; i < count.length; i++) {
        while (count[i]-- > 0) arr[index++] = i;
    }
}

9. Bucket Sort

Bucket sort distributes elements into a number of buckets, sorts each bucket individually (often using another sorting algorithm), and concatenates the results.

Works well when input is uniformly distributed over a range.

public static void sort(int[] arr) {
    int max = arr[0], min = arr[0];
    for (int v : arr) { if (v > max) max = v; if (v < min) min = v; }
    int diff = max - min;
    int length = arr.length;
    List
> buckets = new ArrayList<>();
    for (int i = 0; i < length; i++) buckets.add(new ArrayList<>());
    float section = (float) diff / (length - 1);
    for (int v : arr) {
        int idx = (int) ((v - min) / section);
        if (idx < 0) idx = 0;
        buckets.get(idx).add(v);
    }
    int index = 0;
    for (List
bucket : buckets) {
        Collections.sort(bucket);
        for (int v : bucket) arr[index++] = v;
    }
}

10. Radix Sort

Radix sort processes integer keys digit by digit, from least significant to most significant, using a stable sub‑sorting method (often counting sort) for each digit.

Time complexity O(d·(n + k)) where d is the number of digits; space O(n + k).

public static void sort(int[] arr) {
    int max = arr[0];
    for (int v : arr) if (v > max) max = v;
    int exp = 1; // 10^i
    List
> buckets = new ArrayList<>();
    for (int i = 0; i < 10; i++) buckets.add(new ArrayList<>());
    while (max / exp > 0) {
        for (int v : arr) {
            int bucket = (v / exp) % 10;
            buckets.get(bucket).add(v);
        }
        int idx = 0;
        for (List
bucket : buckets) {
            for (int v : bucket) arr[idx++] = v;
            bucket.clear();
        }
        exp *= 10;
    }
}

The article concludes by thanking the reader and noting that the ten algorithms covered constitute the most commonly used sorting techniques in practice.