MediumArrayDivide and ConquerSortingQuickselect

Quick Sort

1 approach, code in every language

Given an integer array nums, rearrange its elements in place so they end up in non-decreasing order, and return the sorted array. As with any sorting exercise here, you should implement the ordering logic yourself rather than calling a library sort.

Quicksort is the divide-and-conquer strategy of choosing a pivot, partitioning the remaining values into those below and those above the pivot, and then sorting each side. Choosing the pivot at random keeps the expected running time at O(n log n) even when the input is already ordered or contains long runs.

Example 1

Input: nums = [9, 3, 7, 1, 8, 2]

Output: [1, 2, 3, 7, 8, 9]

Partitioning around pivots gradually places every value in its final slot.

Example 2

Input: nums = [4, 4, 1, 2]

Output: [1, 2, 4, 4]

Repeated values are handled without issue by the partition step.

Constraints

1 <= nums.length <= 5 * 10^4
-5 * 10^4 <= nums[i] <= 5 * 10^4

Randomized Quicksort

Pick a random pivot, partition around it in place, then recurse on the two sides.

Loading animation…

Intuition

After a partition step the pivot lands in its correct final position, with all smaller elements to its left and all larger ones to its right. Neither side needs to know about the other, so the algorithm recurses independently on each. The catch is that a poorly chosen pivot (for example, always taking the last element of an already-sorted array) degrades to quadratic time. Selecting the pivot uniformly at random makes those bad splits vanishingly unlikely, so the expected work stays O(n log n) while the sort remains fully in place.

Algorithm walkthrough

1Call quicksort on the full index range [0, length - 1].
2If the range has fewer than two elements it is already sorted, so stop.
3Swap a randomly chosen element to the end to act as the pivot, then scan the range moving every value smaller than the pivot to the front.
4Swap the pivot into the boundary position; it is now in its final sorted location.
5Recurse on the sub-range left of the pivot and the sub-range right of the pivot.

Implementation

import random
from typing import List


class Solution:
    def sortArray(self, nums: List[int]) -> List[int]:
        self._quicksort(nums, 0, len(nums) - 1)
        return nums

    def _quicksort(self, nums: List[int], lo: int, hi: int) -> None:
        if lo >= hi:
            return
        p = self._partition(nums, lo, hi)
        self._quicksort(nums, lo, p - 1)
        self._quicksort(nums, p + 1, hi)

    def _partition(self, nums: List[int], lo: int, hi: int) -> int:
        r = random.randint(lo, hi)
        nums[r], nums[hi] = nums[hi], nums[r]
        pivot = nums[hi]
        i = lo
        for j in range(lo, hi):
            if nums[j] < pivot:
                nums[i], nums[j] = nums[j], nums[i]
                i += 1
        nums[i], nums[hi] = nums[hi], nums[i]
        return i

Time

O(n log n) expected

Space

O(log n)

Worst case is O(n^2), made improbable by the random pivot; space is the recursion stack.

Create a free account to see the solution

You get the step-by-step animation, the intuition and clean code in every language. Free, no credit card.

Create a free account Already have an account? Sign in

Back to Recursion

After the pattern

Now solve one you haven't seen.

Reading a pattern isn't the same as using it. The practice set has 1,194 original problems on the same techniques, each graded in your browser.

Open the practice set Start the FDE path

1,194 problems · 15,062 graded tests · free