Master the Top 10 Sorting Algorithms: Concepts, Code, and Visual Guides

Top 10 Sorting Algorithm Approaches

During technical interviews, candidates often need to write sorting algorithms by hand, so this article summarizes the main ideas of ten classic sorts without diving into low‑level details.

Exchange sorts : sort by repeatedly swapping elements.

Insertion sorts : split the array into a sorted part and an unsorted part, inserting each unsorted element into the correct position.

Selection sorts : repeatedly find the minimum or maximum element and place it at the end of the sorted portion.

Counting sort and radix sort can be viewed as special cases of bucket sort; they do not rely on element comparisons.

Bubble Sort

Bubble sort repeatedly compares adjacent elements and swaps them if they are out of order, bubbling the largest element to the end of the array after each pass.

public static void bubbleSort(int[] a) {
    // Perform i rounds of comparison
    for (int i = 0; i < a.length - 1; i++) {
        for (int j = 0; j < a.length - 1 - i; j++) {
            if (a[j] > a[j + 1]) {
                swap(a, j, j + 1);
            }
        }
    }
}

public static void swap(int[] a, int i, int j) {
    int temp = a[i];
    a[i] = a[j];
    a[j] = temp;
}

Quick Sort

Quick sort works in three steps: choose a pivot, partition the array so that elements smaller than the pivot are on the left and larger ones on the right, then recursively sort the two sub‑arrays.

Pick a pivot element from the array.

Partition: move all elements greater than the pivot to its right and all smaller or equal elements to its left.

Recursively apply step 2 to the left and right sub‑arrays until each sub‑array contains a single element.

public static void quickSort(int[] a, int left, int right) {
    if (left >= right) {
        return;
    }
    int index = sort(a, left, right);
    quickSort(a, left, index - 1);
    quickSort(a, index + 1, right);
}

public static int sort(int[] a, int left, int right) {
    int key = a[left];
    while (left < right) {
        while (left < right && a[right] >= key) {
            right--;
        }
        a[left] = a[right];
        while (left < right && a[left] <= key) {
            left++;
        }
        a[right] = a[left];
    }
    a[left] = key;
    return left;
}

Insertion Sort

The array is divided into a sorted part and an unsorted part; each unsorted element is inserted into its correct position within the sorted part.

public static void insertionSort(int[] a) {
    for (int i = 1; i < a.length; i++) {
        int temp = a[i];
        int j;
        // Find the correct position for temp
        for (j = i - 1; j >= 0 && a[j] > temp; j--) {
            a[j + 1] = a[j];
        }
        a[j + 1] = temp;
    }
}

Shell Sort

Shell sort improves insertion sort by first sorting elements far apart (using a large gap) and gradually reducing the gap, which reduces the total number of moves.

public static void shellSort(int[] a) {
    for (int step = a.length / 2; step > 0; step /= 2) {
        for (int i = step; i < a.length; i++) {
            int temp = a[i];
            int j;
            for (j = i - step; j >= 0 && a[j] > temp; j -= step) {
                a[j + step] = a[j];
            }
            a[j + step] = temp;
        }
    }
}

Selection Sort

Each iteration selects the smallest (or largest) element from the unsorted portion and swaps it into its final position.

public static void selectionSort(int[] a) {
    for (int i = 0; i < a.length; i++) {
        int index = i;
        for (int j = i + 1; j < a.length; j++) {
            if (a[index] > a[j]) {
                index = j;
            }
        }
        if (index != i) {
            swap(a, index, i);
        }
    }
}

Heap Sort

A heap is a complete binary tree that satisfies the heap property: each parent node is greater than (max‑heap) or less than (min‑heap) its children. In an array representation, the parent of index i is (i‑1)/2, left child is 2*i+1, right child is 2*i+2.

public class HeapSort {
    public static void heapSort(int[] a) {
        buildTree(a);
        for (int i = a.length - 1; i >= 0; i--) {
            swap(a, i, 0);
            heapify(a, i, 0);
        }
    }

    public static void buildTree(int[] a) {
        int lastNode = a.length - 1;
        int parent = (lastNode - 1) / 2;
        for (int i = parent; i >= 0; i--) {
            heapify(a, a.length, i);
        }
    }

    /**
     * @param a array
     * @param n length of the heap to consider
     * @param i index to heapify
     */
    public static void heapify(int[] a, int n, int i) {
        if (i >= n) return;
        int c1 = 2 * i + 1;
        int c2 = 2 * i + 2;
        int max = i;
        if (c1 < n && a[c1] > a[max]) max = c1;
        if (c2 < n && a[c2] > a[max]) max = c2;
        if (max != i) {
            swap(a, max, i);
            heapify(a, n, max);
        }
    }

    public static void swap(int[] a, int i, int j) {
        int temp = a[i];
        a[i] = a[j];
        a[j] = temp;
    }
}

Heap insertion and deletion follow the same heap property: new elements are added at the end of the array and then “bubble up”, while removal replaces the root with the last element and then “heapifies” down.

Counting Sort

Counting sort creates a frequency array where count[i] records how many times value i appears in the input. It is efficient when the range of input values is limited.

public static void countingSort(int[] a) {
    int max = Integer.MIN_VALUE;
    for (int num : a) {
        max = Integer.max(max, num);
    }
    int[] count = new int[max + 1];
    for (int num : a) {
        count[num]++;
    }
    int index = 0;
    for (int i = 0; i < count.length; i++) {
        while (count[i] > 0) {
            a[index++] = i;
            count[i]--;
        }
    }
}

An improved version handles arbitrary minimum values by offsetting the index with the smallest element.

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

Merge Sort

Merge sort recursively splits the array into single‑element sub‑arrays and then merges them back together in sorted order.

public static void mergeSort(int[] a, int left, int right) {
    if (left == right) return;
    int mid = (left + right) / 2;
    mergeSort(a, left, mid);
    mergeSort(a, mid + 1, right);
    merge(a, left, mid, right);
}

public static void merge(int[] a, int left, int mid, int right) {
    int[] temp = new int[right - left + 1];
    int i = left, j = mid + 1, k = 0;
    while (i <= mid && j <= right) {
        if (a[i] < a[j]) temp[k++] = a[i++];
        else temp[k++] = a[j++];
    }
    while (i <= mid) temp[k++] = a[i++];
    while (j <= right) temp[k++] = a[j++];
    for (int p = 0; p < temp.length; p++) {
        a[left + p] = temp[p];
    }
}

Radix Sort

Radix sort processes each digit of the numbers (from least to most significant) using a stable counting sort as a sub‑routine. It is rarely asked in interviews, so details are omitted here.

Bucket Sort

Bucket sort distributes elements into a number of buckets, sorts each bucket (often with insertion sort), and then concatenates them. Counting sort and radix sort can be seen as special cases of bucket sort that avoid element‑wise comparisons.

Applications of Sorting Algorithms

Common interview questions such as “Top‑K” problems can be solved by sorting the entire array and picking the first K elements, but more efficient solutions use a heap or quick‑select. The following table shows typical time complexities of the discussed algorithms:

For large‑scale data, using a heap (priority queue) or quick‑select yields better performance than full sorting.