Quick Sort

Given an array of integers nums, sort the array in ascending order and return it.

You must solve the problem without using any built-in functions in O(n log n) time complexity and with the smallest space complexity possible.

Example 1:

Input: nums = [5,2,3,1] Output: [1,2,3,5] Explanation: After sorting the array, the positions of some numbers are not changed (for example, 2 and 3), while the positions of other numbers are changed (for example, 1 and 5).

Example 2:

Input: nums = [5,1,1,2,0,0] Output: [0,0,1,1,2,5] Explanation: Note that the values of nums are not necessarily unique.

Constraints:

• 1 <= nums.length <= 5 * 104
• -5 * 104 <= nums[i] <= 5 * 104

Approach: Quick Sort (Divide and Conquer, In-Place)

Algorithm

1. Choose a pivot element (here: the rightmost element)
2. Partition: Rearrange the array so all elements smaller than the pivot come before it and all larger elements come after it
3. Recurse: Recursively apply the same process to the subarrays on the left and right of the pivot
4. The pivot is now in its final sorted position

Time & Space Complexity

• Time Complexity: O(n log n) average, O(n²) worst case (e.g., already sorted input with a bad pivot)
• Space Complexity: O(log n) average - recursion stack

Java Implementation

public class QuickSort {

    /**
     * Sort an array in ascending order using quick sort.
     * @param nums Input array
     * @return Sorted array
     */
    public static int[] sortArray(int[] nums) {
        quickSort(nums, 0, nums.length - 1);
        return nums;
    }

    private static void quickSort(int[] nums, int lo, int hi) {
        if (lo >= hi) {
            return;
        }

        int pivotIndex = partition(nums, lo, hi);
        quickSort(nums, lo, pivotIndex - 1);
        quickSort(nums, pivotIndex + 1, hi);
    }

    private static int partition(int[] nums, int lo, int hi) {
        int pivot = nums[hi];
        int i = lo; // boundary of elements smaller than pivot

        for (int j = lo; j < hi; j++) {
            if (nums[j] < pivot) {
                swap(nums, i, j);
                i++;
            }
        }

        swap(nums, i, hi);
        return i;
    }

    private static void swap(int[] nums, int a, int b) {
        int tmp = nums[a];
        nums[a] = nums[b];
        nums[b] = tmp;
    }

    // Test method
    public static void main(String[] args) {
        int[] nums1 = {5, 2, 3, 1};
        System.out.println("Input: nums = [5, 2, 3, 1]");
        System.out.println("Output: " + java.util.Arrays.toString(sortArray(nums1)));
        // Expected: [1, 2, 3, 5]

        int[] nums2 = {5, 1, 1, 2, 0, 0};
        System.out.println("Input: nums = [5, 1, 1, 2, 0, 0]");
        System.out.println("Output: " + java.util.Arrays.toString(sortArray(nums2)));
        // Expected: [0, 0, 1, 1, 2, 5]
    }
}

Example Walkthrough

For nums = [5, 2, 3, 1] (pivot = 1):

1. Partition around 1: [1, 2, 3, 5], pivot at index 0
2. Recurse on right [2, 3, 5] (pivot = 5): no element larger, pivot stays at end
3. Recurse on [2, 3] (pivot = 3): 2 < 3, pivot stays. Recurse on [2]
4. Array fully sorted: [1, 2, 3, 5]

Key Points

1. In-Place: Sorting happens within the original array with only swaps
2. Partitioning Core: The partition step places the pivot in its final position
3. Average vs Worst Case: Random or median-of-three pivots avoid the O(n²) worst case
4. Not Stable: Equal elements may change relative order
5. Quickselect: The partition step is reused to find the kth largest element in O(n) average time