Common Sorting Algorithms

Sorting Algorithms Overview

Stability: Whether equal elements maintain their relative order after sorting.

Insertion Sort

Logic: Maintain a sorted prefix and insert new elements into their correct position within that prefix. Similar to organizing a hand of playing cards.

void insertionSort(int[] arr) {
    for (int i = 1; i < arr.length; i++) {
        int key = arr[i]; // Element to be inserted
        int j = i - 1;
        // Shift larger elements to the right to create a slot for 'key'
        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];
            j--;
        }
        arr[j + 1] = key; // Place key in its sorted position
    }
}

Advantage: For nearly sorted arrays, insertion sort performs in close to O(N) time. Many language libraries use insertion sort as a fallback for small arrays ($N < 16$).

Quicksort

Logic: Choose a pivot element and partition the array around it (elements smaller to the left, larger to the right). Recursively repeat for both halves.

void quickSort(int[] arr, int left, int right) {
    if (left >= right) return;
    int pivotIndex = partition(arr, left, right);
    quickSort(arr, left, pivotIndex - 1);
    quickSort(arr, pivotIndex + 1, right);
}

// Lomuto Partitioning Scheme (using the last element as the pivot)
int partition(int[] arr, int left, int right) {
    int pivot = arr[right];
    int i = left - 1; // Tracks the boundary of the 'smaller' partition
    for (int j = left; j < right; j++) {
        if (arr[j] <= pivot) {
            i++;
            swap(arr, i, j);
        }
    }
    swap(arr, i + 1, right); // Place pivot in the middle
    return i + 1;
}

private void swap(int[] arr, int i, int j) {
    int temp = arr[i]; arr[i] = arr[j]; arr[j] = temp;
}

Randomization: To prevent O(N²) degradation on sorted inputs, pick a random pivot:

int randomPivot = left + (int)(Math.random() * (right - left + 1));
swap(arr, randomPivot, right); // Move random pivot to the end

Quick Select (K-th Element)

The partitioning logic can find the $k$-th smallest element in $O(N)$ average time without sorting the whole array:

int findKthSmallest(int[] nums, int k) {
    int l = 0, r = nums.length - 1;
    while (l <= r) {
        int p = partition(nums, l, r);
        if (p == k - 1) return nums[p];
        else if (p < k - 1) l = p + 1;
        else r = p - 1;
    }
    return -1;
}

Merge Sort

Logic: Divide and Conquer—split the array into two halves, recursively sort them, and then merge the two sorted halves back together.

int[] mergeSort(int[] arr) {
    if (arr.length <= 1) return arr;
    int mid = arr.length / 2;
    int[] leftHalf = mergeSort(Arrays.copyOfRange(arr, 0, mid));
    int[] rightHalf = mergeSort(Arrays.copyOfRange(arr, mid, arr.length));
    return merge(leftHalf, rightHalf);
}

int[] merge(int[] left, int[] right) {
    int[] results = new int[left.length + right.length];
    int i = 0, j = 0, k = 0;
    while (i < left.length && j < right.length) {
        if (left[i] <= right[j]) results[k++] = left[i++]; // <= ensures stability
        else results[k++] = right[j++];
    }
    while (i < left.length) results[k++] = left[i++];
    while (j < right.length) results[k++] = right[j++];
    return results;
}

Advantages:

• Stable: Preserves relative order of equal elements.
• Worst-case O(N log N): Consistent performance regardless of input data.
• Linked Lists: Ideal for linked lists as it only requires pointer changes.

Heap Sort

Logic: Build a Max Heap from the array. Repeatedly extract the root (maximum element), swap it with the last element, and re-heapify the remaining heap.

public void heapSort(int[] arr) {
    int n = arr.length;
    // 1. Build Max Heap
    for (int i = n / 2 - 1; i >= 0; i--) heapify(arr, n, i);
    // 2. Extract elements
    for (int i = n - 1; i > 0; i--) {
        swap(arr, 0, i);    // Move max to the end
        heapify(arr, i, 0); // Shrink heap and restore property
    }
}

void heapify(int[] arr, int n, int i) {
    int largest = i;
    int l = 2 * i + 1, r = 2 * i + 2;
    if (l < n && arr[l] > arr[largest]) largest = l;
    if (r < n && arr[r] > arr[largest]) largest = r;
    
    if (largest != i) {
        swap(arr, i, largest);
        heapify(arr, n, largest); // Recursively sink down
    }
}

Non-Comparative Sorting

When the range of values is constrained, we can achieve $O(N)$ linear time.

Counting Sort

void countingSort(int[] arr) {
    int max = Arrays.stream(arr).max().getAsInt();
    int[] frequency = new int[max + 1];
    for (int x : arr) frequency[x]++;
    
    int index = 0;
    for (int val = 0; val <= max; val++) {
        while (frequency[val]-- > 0) arr[index++] = val;
    }
}

Usage: Highly efficient when the range of values $K$ is small ($K \approx N$).

Java Internal Sorting

Arrays.sort(intArray);           // Primitives: Dual-Pivot Quicksort (O(N log N), Unstable, In-place)
Arrays.sort(objectArray);        // Objects: TimSort (O(N log N), Stable, uses extra space)

// Comparator (requires object arrays)
Integer[] nums = {3, 1, 2};
Arrays.sort(nums, (a, b) -> b - a); // Descending order

// Sorting Custom Objects
Arrays.sort(intervals, (a, b) -> a[0] - b[0]); // Sort by start time ascending

Note: For primitives, Arrays.sort is optimized for speed but NOT stable. If stability is required for primitives, you must convert them to a Wrapper class array (e.g., Integer[]) first.

Strategy Cheat Sheet

• Small data ($N < 20$): Insertion Sort (Low constant factors).
• Nearly sorted data: Insertion Sort.
• Stability required: Merge Sort (or Arrays.sort for objects).
• General purpose: Quicksort (Fastest in practice with randomization).
• No extra memory ($O(1)$ space): Heap Sort.
• Small fixed range of integers: Counting Sort.

Summary Comparison