QuickSort.java

package sorting;

import java.util.Arrays;

/**
 * QuickSort class implements the QuickSort algorithm using
 * the Median-of-Three pivot selection strategy to improve performance
 * and avoid worst-case behavior on sorted or nearly sorted input.
 *
 * <p>Time Complexity:
 * - Best Case:    O(n log n)
 * - Average Case: O(n log n)
 * - Worst Case:   O(n^2) [minimized by good pivot choice]
 *
 * <p>Space Complexity:
 * - O(log n) due to recursion stack (in balanced cases)
 */
public class QuickSort {
    public static void main(String[] args) {
        int[] arr = {4, 6, 2, 5, 7, 9, 1, 3};
        quickSort(arr, 0, arr.length - 1);
        System.out.println(Arrays.toString(arr));
    }

    static void quickSort(int[] arr, int l, int r) {
        // if there are more than 2 elements in the array
        if (l < r) {
            int pivotIndex = medianOfThree(arr, l, r);
            swap(arr, l, pivotIndex); // Move pivot to start
            int p = partition(arr, l, r);
            quickSort(arr, l, p - 1);
            quickSort(arr, p + 1, r);
        }
    }

    static int partition(int[] a, int l, int r) {
        int pivot = a[l];
        int i = l + 1, j = r;

        while (i <= j) {
            // If all values are <= pivot, then i could increment past r,
            // leading to array index out of bound exception
            while (i <= r && a[i] <= pivot) i++;
            // If all values are greater than pivot on the left side then
            // j could decrement past 0, leading to out of bound exception
            while (j >= 0 && a[j] > pivot) j--;
            if (i < j) swap(a, i, j);
        }
        swap(a, l, j);
        return j;
    }

    private static int medianOfThree(int[] arr, int l, int r) {
        int m = l + (r - l) / 2;

        if (arr[l] > arr[m]) swap(arr, l, m);
        if (arr[l] > arr[r]) swap(arr, l, r);
        if (arr[m] > arr[r]) swap(arr, m, r);

        return m; // Return index of median
    }

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

}