Skip to main content

​
Sorting Algorithms

Sorting is one of the most fundamental operations in computer science. This guide covers all major sorting algorithms with Java implementations.

​
Algorithm Comparison

AlgorithmBestAverageWorstSpaceStable
Bubble SortO(n)O(n²)O(n²)O(1)✅
Selection SortO(n²)O(n²)O(n²)O(1)❌
Insertion SortO(n)O(n²)O(n²)O(1)✅
Quick SortO(n log n)O(n log n)O(n²)O(log n)❌
Merge SortO(n log n)O(n log n)O(n log n)O(n)✅
Heap SortO(n log n)O(n log n)O(n log n)O(1)❌
Shell SortO(n log n)O(n^1.3)O(n²)O(1)❌

​
Bubble Sort

Bubble Sort repeatedly compares adjacent elements and swaps them if they’re in the wrong order.

​
Implementation

public class BubbleSort {
    public static void sort(int[] arr) {
        int n = arr.length;
        for (int i = 0; i < n; i++) {
            // Last i elements are already sorted
            for (int j = 0; j < n - i - 1; j++) {
                if (arr[j] > arr[j + 1]) {
                    // Swap arr[j] and arr[j+1]
                    int temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                }
            }
        }
    }
}
Add a flag to detect if any swaps occurred in a pass:
public static void bubbleSortOptimized(int[] arr) {
    int n = arr.length;
    for (int i = 0; i < n; i++) {
        boolean swapped = false;
        for (int j = 0; j < n - i - 1; j++) {
            if (arr[j] > arr[j + 1]) {
                int temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
                swapped = true;
            }
        }
        // If no swaps occurred, array is sorted
        if (!swapped) break;
    }
}

​
Selection Sort

Selection Sort finds the minimum element and places it at the beginning. 
public class SelectionSort {
    public static void sort(int[] arr) {
        int n = arr.length;
        for (int i = 0; i < n - 1; i++) {
            int minIndex = i;
            // Find minimum element in unsorted part
            for (int j = i + 1; j < n; j++) {
                if (arr[j] < arr[minIndex]) {
                    minIndex = j;
                }
            }
            // Swap minimum with first unsorted element
            int temp = arr[i];
            arr[i] = arr[minIndex];
            arr[minIndex] = temp;
        }
    }
}

​
Insertion Sort

Insertion Sort builds the sorted array one element at a time. 
public class InsertionSort {
    public static void sort(int[] arr) {
        int n = arr.length;
        for (int i = 1; i < n; i++) {
            int key = arr[i];
            int j = i - 1;
            
            // Move elements greater than key one position ahead
            while (j >= 0 && arr[j] > key) {
                arr[j + 1] = arr[j];
                j--;
            }
            arr[j + 1] = key;
        }
    }
}
Insertion Sort performs excellently on nearly sorted arrays and is the algorithm of choice for small arrays (typically < 10 elements).

​
Quick Sort

Quick Sort uses a divide-and-conquer approach with a pivot element.

​
Implementation

public class QuickSort {
    public static void sort(int[] arr, int left, int right) {
        if (left >= right) return;
        
        int pivotIndex = partition(arr, left, right);
        sort(arr, left, pivotIndex - 1);
        sort(arr, pivotIndex + 1, right);
    }
    
    private static int partition(int[] arr, int left, int right) {
        int pivot = arr[left];
        int j = left; // Last element in smaller partition
        
        for (int i = left + 1; i <= right; i++) {
            if (arr[i] < pivot) {
                j++;
                swap(arr, i, j);
            }
        }
        swap(arr, left, j);
        return j;
    }
    
    private static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}
Given array [3, 1, 5, 6, 2]:
  1. Choose pivot (3)
  2. Partition: elements < pivot go left, >= pivot go right
  3. After partition: [1, 2, 3, 6, 5]
  4. Recursively sort left [1, 2] and right [6, 5]
  5. Final result: [1, 2, 3, 5, 6]

​
Merge Sort

Merge Sort divides the array recursively and merges sorted subarrays. 
public class MergeSort {
    public static void sort(int[] arr, int left, int right) {
        if (left >= right) return;
        
        int mid = left + (right - left) / 2;
        sort(arr, left, mid);
        sort(arr, mid + 1, right);
        merge(arr, left, mid, right);
    }
    
    private static void merge(int[] arr, int left, int mid, int right) {
        int[] temp = new int[arr.length];
        
        // Copy elements to temp array
        for (int k = left; k <= right; k++) {
            temp[k] = arr[k];
        }
        
        int i = left, j = mid + 1, k = left;
        
        // Merge back to arr
        while (k <= right) {
            if (i == mid + 1) {
                arr[k++] = temp[j++];
            } else if (j == right + 1 || temp[i] <= temp[j]) {
                arr[k++] = temp[i++];
            } else {
                arr[k++] = temp[j++];
            }
        }
    }
}

class Solution {
    public ListNode sortList(ListNode head) {
        if (head == null || head.next == null) return head;
        
        // Find middle using slow-fast pointers
        ListNode slow = head, fast = head;
        while (fast.next != null && fast.next.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        
        ListNode mid = slow.next;
        slow.next = null;
        
        ListNode left = sortList(head);
        ListNode right = sortList(mid);
        
        return merge(left, right);
    }
    
    private ListNode merge(ListNode l1, ListNode l2) {
        ListNode dummy = new ListNode(0);
        ListNode curr = dummy;
        
        while (l1 != null && l2 != null) {
            if (l1.val < l2.val) {
                curr.next = l1;
                l1 = l1.next;
            } else {
                curr.next = l2;
                l2 = l2.next;
            }
            curr = curr.next;
        }
        
        curr.next = (l1 != null) ? l1 : l2;
        return dummy.next;
    }
}

​
Heap Sort

Heap Sort uses a binary heap data structure. 
public class HeapSort {
    public static void sort(int[] arr) {
        int n = arr.length;
        
        // Build max heap
        for (int i = n / 2 - 1; i >= 0; i--) {
            heapify(arr, n, i);
        }
        
        // Extract elements from heap one by one
        for (int i = n - 1; i > 0; i--) {
            swap(arr, 0, i);
            heapify(arr, i, 0);
        }
    }
    
    private static void heapify(int[] arr, int n, int i) {
        int largest = i;
        int left = 2 * i + 1;
        int right = 2 * i + 2;
        
        if (left < n && arr[left] > arr[largest]) {
            largest = left;
        }
        if (right < n && arr[right] > arr[largest]) {
            largest = right;
        }
        
        if (largest != i) {
            swap(arr, i, largest);
            heapify(arr, n, largest);
        }
    }
    
    private static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}

​
Shell Sort

Shell Sort is an optimization of Insertion Sort using gap sequences. 
public class ShellSort {
    public static void sort(int[] arr) {
        int n = arr.length;
        
        // Start with large gap, reduce by half each iteration
        for (int gap = n / 2; gap > 0; gap /= 2) {
            for (int i = gap; i < n; i++) {
                int temp = arr[i];
                int j = i;
                
                while (j >= gap && arr[j - gap] > temp) {
                    arr[j] = arr[j - gap];
                    j -= gap;
                }
                arr[j] = temp;
            }
        }
    }
}

​
Practical Applications

​
When to Use Each Algorithm

Use Insertion Sort: Simple, efficient for small datasets, minimal overhead
Use Insertion Sort: Best case O(n) when data is already sorted
Use Quick Sort: Average O(n log n), in-place sorting, cache-friendly
Use Merge Sort or Heap Sort: Worst case O(n log n), predictable performance
Use Merge Sort: Maintains relative order of equal elements
Use Heap Sort or Quick Sort: O(1) or O(log n) space complexity

​
Common Interview Problems

Sort Colors

Dutch National Flag problem - sort array with 3 distinct values

Merge Intervals

Sort intervals by start time, then merge overlapping ones

Largest Number

Custom comparator to arrange numbers forming largest value

Meeting Rooms

Sort meetings by start time to check for conflicts
Common Mistakes:
  • Forgetting to handle equal elements in stable sorts
  • Not considering worst-case scenarios for Quick Sort
  • Incorrect partition logic leading to infinite recursion
  • Off-by-one errors in array bounds

Build docs developers (and LLMs) love

Get started for freeTalk to us