Quick Sort Explained: How It Works, Why It's Fast, and When to Use It

public class QuickSortLomuto {

    /**
     * Entry point — sorts the array in-place between indices 'low' and 'high'.
     * We pass indices rather than creating sub-arrays, so no extra memory is needed.
     */
    public static void quickSort(int[] numbers, int low, int high) {
        // Base case: a sub-array of 0 or 1 elements is already sorted — nothing to do.
        if (low >= high) return;

        // Partition the array and get back the pivot's final resting index.
        int pivotFinalIndex = partition(numbers, low, high);

        // Recursively sort everything to the LEFT of the pivot (pivot itself is already placed).
        quickSort(numbers, low, pivotFinalIndex - 1);

        // Recursively sort everything to the RIGHT of the pivot.
        quickSort(numbers, pivotFinalIndex + 1, high);
    }

    /**
     * Lomuto Partition Scheme.
     * Chooses the LAST element as the pivot, then rearranges the sub-array so that:
     *   - All elements <= pivot are to the left of storeIndex
     *   - All elements >  pivot are to the right of storeIndex
     * Returns storeIndex — the pivot's correct final position.
     */
    private static int partition(int[] numbers, int low, int high) {
        int pivot = numbers[high]; // We always pick the last element as pivot (simple but has pitfalls — see Gotchas)
        int storeIndex = low - 1; // storeIndex tracks the boundary between "small" and "large" elements

        for (int scanner = low; scanner < high; scanner++) {
            if (numbers[scanner] <= pivot) {
                storeIndex++;  // Expand the "small" region by one slot
                swap(numbers, storeIndex, scanner); // Pull this small element into the small region
            }
        }

        // Place the pivot right after all the small elements — this is its final position.
        swap(numbers, storeIndex + 1, high);

        return storeIndex + 1; // Return the pivot's final index so quickSort knows where to split
    }

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

    public static void main(String[] args) {
        int[] scores = {42, 17, 93, 5, 61, 38, 72, 29};

        System.out.println("Before sorting:");
        printArray(scores);

        quickSort(scores, 0, scores.length - 1);

        System.out.println("After sorting:");
        printArray(scores);
    }

    private static void printArray(int[] numbers) {
        System.out.print("[ ");
        for (int number : numbers) System.out.print(number + " ");
        System.out.println("]");
    }
}

public class QuickSortMedianOfThree {

    public static void quickSort(int[] numbers, int low, int high) {
        if (low >= high) return;

        // Choose a smarter pivot BEFORE partitioning
        choosePivotMedianOfThree(numbers, low, high);

        int pivotFinalIndex = partition(numbers, low, high);
        quickSort(numbers, low, pivotFinalIndex - 1);
        quickSort(numbers, pivotFinalIndex + 1, high);
    }

    /**
     * Median-of-Three Pivot Selection.
     * Looks at the first, middle, and last elements.
     * Rearranges so the median value ends up at numbers[high] — ready for Lomuto.
     * This prevents O(n²) behaviour on already-sorted input.
     */
    private static void choosePivotMedianOfThree(int[] numbers, int low, int high) {
        int mid = low + (high - low) / 2; // Avoids integer overflow (important for large arrays)

        // Sort just these three candidates so numbers[mid] holds the median
        if (numbers[low] > numbers[mid])  swap(numbers, low, mid);
        if (numbers[low] > numbers[high]) swap(numbers, low, high);
        if (numbers[mid] > numbers[high]) swap(numbers, mid, high);

        // Now numbers[high] is the median of the three — perfect Lomuto pivot
    }

    private static int partition(int[] numbers, int low, int high) {
        int pivot = numbers[high];
        int storeIndex = low - 1;

        for (int scanner = low; scanner < high; scanner++) {
            if (numbers[scanner] <= pivot) {
                storeIndex++;
                swap(numbers, storeIndex, scanner);
            }
        }

        swap(numbers, storeIndex + 1, high);
        return storeIndex + 1;
    }

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

    public static void main(String[] args) {
        // This input would cause O(n²) with naive last-element pivot — median-of-three handles it fine
        int[] alreadySorted = {10, 20, 30, 40, 50, 60, 70, 80, 90, 100};

        System.out.println("Sorting already-sorted data (Quick Sort's classic nemesis):");
        System.out.print("Before: ");
        printArray(alreadySorted);

        quickSort(alreadySorted, 0, alreadySorted.length - 1);

        System.out.print("After:  ");
        printArray(alreadySorted);

        // Also demonstrate on random data
        int[] playerScores = {88, 34, 67, 12, 99, 45, 23, 78, 56, 11};
        System.out.println("\nSorting game leaderboard scores:");
        System.out.print("Before: ");
        printArray(playerScores);

        quickSort(playerScores, 0, playerScores.length - 1);

        System.out.print("After:  ");
        printArray(playerScores);
    }

    private static void printArray(int[] numbers) {
        System.out.print("[ ");
        for (int n : numbers) System.out.print(n + " ");
        System.out.println("]");
    }
}

import java.util.Arrays;
import java.util.Comparator;

public class SortingComparison {

    // A real-world object: an employee with two sortable fields
    static class Employee {
        String name;
        String department;
        int hireOrder; // Lower = hired earlier (already sorted by this field)

        Employee(String name, String department, int hireOrder) {
            this.name = name;
            this.department = department;
            this.hireOrder = hireOrder;
        }

        @Override
        public String toString() {
            return name + "(" + department + ", hire#" + hireOrder + ")";
        }
    }

    public static void main(String[] args) {
        // Employees are already ordered by hireOrder (1 through 6)
        Employee[] employees = {
            new Employee("Alice",   "Engineering", 1),
            new Employee("Bob",     "Marketing",   2),
            new Employee("Carol",   "Engineering", 3),
            new Employee("David",   "Marketing",   4),
            new Employee("Eve",     "Engineering", 5),
            new Employee("Frank",   "Marketing",   6)
        };

        System.out.println("Original order (sorted by hire date):");
        printEmployees(employees);

        // Sort by department using Arrays.sort — which uses TimSort (STABLE) for objects
        Arrays.sort(employees, Comparator.comparing(e -> e.department));

        System.out.println("\nAfter sorting by department (TimSort — STABLE):");
        printEmployees(employees);
        // Notice: within Engineering, Alice(1) still comes before Carol(3) before Eve(5)
        // Their hire order is PRESERVED. This is what stable sort guarantees.

        System.out.println("\nWithin each department, hire order is preserved — that's stability in action.");

        // For primitives, Arrays.sort uses Dual-Pivot QuickSort (NOT stable, but very fast)
        int[] responseTimes = {120, 45, 300, 89, 12, 456, 67, 23};
        System.out.println("\nAPI response times (ms) before sort: " + Arrays.toString(responseTimes));
        Arrays.sort(responseTimes); // Dual-Pivot QuickSort under the hood
        System.out.println("API response times (ms) after sort:  " + Arrays.toString(responseTimes));
    }

    private static void printEmployees(Employee[] employees) {
        for (Employee e : employees) System.out.print(e + "  ");
        System.out.println();
    }
}