Start learning free

LESSON 256 OF 338 · DIVIDE AND CONQUER

Quick Sort in Go: O(n log n) with Random Pivots

Practice O(n log n) Read the full explanation

In this video lesson we will study how the Quick Sort algorithm works, we will analyze its time and space complexities and then we will implement it:

Problem - Quick Sort:

Given an array of integers nums, sort it in ascending order using Quick Sort

Example 1:

Input: nums = [3, 1, 3, 2, 5, 4]
Output: [1, 2, 3, 3, 4, 5]

Note:

Your algorithm should run in O(n log n) time and use O(log n) extra space.

STEP 1 OF 16
    Ctrl + Enter to check

    GO · DIVIDE AND CONQUER

    Quick Sort in Go, explained

    Problem overview

    The function sortArray(nums) sorts a slice of integers in ascending order using Quick Sort. It returns nothing and rearranges nums itself. The statement asks for O(n log n) time and O(log n) extra space.

    For nums = [3, 1, 3, 2, 5, 4] the slice becomes [1, 2, 3, 3, 4, 5].

    Approach: partition around a pivot, then sort both sides

    Quick Sort picks one element, the pivot, and rearranges the range so that everything not larger than the pivot sits before it and everything larger sits after it. This step is called partitioning. After it, the pivot is in its final position, and the two sides can be sorted independently, with the same function, without ever merging.

    Compare this with Merge Sort. Merge Sort does its cheap work after the recursive calls, by merging, and needs a buffer of n elements. Quick Sort does the work before the recursive calls, by partitioning, and rearranges the elements in place. Its only extra memory is the call stack.

    The running time depends on how evenly the pivot splits the range. If each pivot lands near the middle, there are about log2(n) levels of O(n) partitioning work, which is O(n log n). If the pivot is always the smallest or largest element, one side is empty each time and the work grows to O(n²). A fixed choice such as always taking the last element does exactly that on input that is already sorted. Choosing the pivot at random makes bad splits unlikely whatever the input order, so the expected time is O(n log n) and the expected recursion depth is O(log n).

    Step by step

    1. Start the recursion. sortArray calls quickSort(nums, 0, len(nums)-1). Both bounds are inclusive.
    2. Declare quickSort with nums []int and left, right int. A slice shares its underlying array, so changes made inside are visible to the caller.
    3. Base case. When left >= right, the range has at most one element and is already sorted, so return.
    4. Partition. Call partition(nums, left, right) and store the pivot's final index in pivot.
    5. Sort the left side, from left to pivot - 1.
    6. Sort the right side, from pivot + 1 to right. The pivot is excluded from both calls because it is already in place.
    7. Declare partition with the same parameters, returning an int.
    8. Pick a random index between left and right. rand.Intn(right-left+1) returns 0 to right-left, and adding left shifts it into the range.
    9. Move the pivot to the end with a tuple assignment, nums[randomIndex], nums[right] = nums[right], nums[randomIndex]. Go evaluates the right side first, so no temporary variable is needed.
    10. Remember the pivot value in value.
    11. Track the boundary. correctIndex starts at left. It is where the next element that is at most value belongs, and everything before it already is.
    12. Scan the range with i from left to right, including right.
    13. Move small elements left. If nums[i] <= value, swap nums[i] with nums[correctIndex] and increase correctIndex.
    14. Return correctIndex - 1. The pivot itself, at index right, is the last element moved to the front, so it ends just before correctIndex.

    The solution in Go

    func sortArray(nums []int) {
	quickSort(nums, 0, len(nums)-1)
}

func quickSort(nums []int, left, right int) {
	if left >= right {
		return
	}
	pivot := partition(nums, left, right)
	quickSort(nums, left, pivot-1)
	quickSort(nums, pivot+1, right)
}

func partition(nums []int, left, right int) int {
	randomIndex := left + rand.Intn(right-left+1)
	nums[randomIndex], nums[right] = nums[right], nums[randomIndex]
	value := nums[right]
	correctIndex := left
	for i := left; i <= right; i++ {
		if nums[i] <= value {
			nums[i], nums[correctIndex] = nums[correctIndex], nums[i]
			correctIndex++
		}
	}
	return correctIndex - 1
}

    Here is one partition by hand. Take [4, 7, 1, 9, 3, 6] and suppose the random pivot is already at the end, so value is 6. The scan swaps 4, 1 and 3 to the front and then the pivot itself, giving [4, 1, 3, 6, 7, 9]. The function returns 3. Everything before index 3 is at most 6 and everything after it is larger.

    Go details worth knowing:

    • The import. rand.Intn comes from the math/rand package, which a complete program must import. Since Go 1.20 that package seeds itself randomly, so no seeding call is needed.
    • Swapping. a, b = b, a is a single statement. When the two positions are the same element, as when i equals correctIndex, the swap does nothing harmful.
    • Sharing the array. Passing nums copies only the slice header. All the calls work on the same elements, so no copying happens and no slice is returned.
    • The loop includes right. The pivot at the end satisfies nums[i] <= value, so it is swapped into its place last. That is why the pivot ends at correctIndex - 1.
    • The empty case is safe. For an empty slice the first call has right = -1 and returns before partition asks the random generator for a number.

    Complexity

    Time: expected O(n log n). Each partition is a single pass over its range, and with random pivots the ranges shrink geometrically on average. The worst case is O(n²), but the random choice makes it extremely unlikely on ordinary input.

    Space: expected O(log n) for the call stack. Nothing else is allocated.

    Edge cases and common mistakes

    • Empty slice and single element. Both end at the base case.
    • Duplicates. [3, 1, 3, 2, 5, 4] sorts correctly because elements equal to the pivot go to its left side. A slice where every element is equal is the exception to the speed guarantee: each partition moves all elements to the left, so the pivot ends at right and the recursion shrinks by one element per call. With 2,000 equal elements the partitions scan about two million positions, which is quadratic. Handling this takes a three-way partition, which this lesson does not use.
    • Negative numbers. Only comparisons are used, so sign doesn't matter. [-3, 8, 0, -3, 2] becomes [-3, -3, 0, 2, 8].
    • Looping to right - 1. That variant needs a final swap to put the pivot in place. This lesson's loop includes right and avoids the extra step.
    • Recursing on the pivot. Calling quickSort(nums, left, pivot) can leave the range unchanged and recurse forever. Use pivot - 1 and pivot + 1.
    • A non-random pivot. Always using nums[right] works but degrades to O(n²) on input that is already sorted.
    • Unstable sort. Equal elements can change their relative order. For plain integers that is invisible.

    Testing

    [3, 1, 3, 2, 5, 4] gives [1, 2, 3, 3, 4, 5]. An empty slice stays empty, [5, 5, 5, 5] stays the same, and [-3, 8, 0, -3, 2] gives [-3, -3, 0, 2, 8].

    Keep going with GoAbout 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free