Quick Sort Algorithm in DSA Go

Mental Model

Quick Sort splits the list into smaller parts around a pivot, sorting each part separately until the whole list is sorted.

Analogy: Imagine sorting a pile of cards by picking one card as a divider, then putting smaller cards on one side and bigger cards on the other, and repeating this for each side until all cards are in order.

Array: [7, 2, 9, 4, 3]
Pivot chosen: 3
Partitioned: [2] [3] [7, 9, 4]

Dry Run Walkthrough

Input: list: [7, 2, 9, 4, 3]

Goal: Sort the list in ascending order using Quick Sort

Step 1: Choose pivot as last element 3, partition array around pivot

[2, 3, 9, 4, 7]

Why: We move elements smaller than pivot to the left, bigger to the right

Step 2: Recursively quick sort left part [2]

[2]

Why: Single element is already sorted

Step 3: Recursively quick sort right part [9, 4, 7]

[4, 7, 9]

Why: Repeat partition and sort on right side

Step 4: Combine sorted parts: left [2], pivot [3], right [4, 7, 9]

[2, 3, 4, 7, 9]

Why: All parts sorted and combined form the sorted array

Result:

[2, 3, 4, 7, 9]

Annotated Code

DSA Go

package main

import "fmt"

func quickSort(arr []int, low, high int) {
    if low < high {
        pi := partition(arr, low, high) // partition array and get pivot index
        quickSort(arr, low, pi-1)       // sort left part
        quickSort(arr, pi+1, high)      // sort right part
    }
}

func partition(arr []int, low, high int) int {
    pivot := arr[high]                 // choose pivot as last element
    i := low - 1                      // index of smaller element
    for j := low; j < high; j++ {
        if arr[j] <= pivot {           // if current element smaller or equal to pivot
            i++                       // move smaller element index forward
            arr[i], arr[j] = arr[j], arr[i] // swap smaller element to front
        }
    }
    arr[i+1], arr[high] = arr[high], arr[i+1] // place pivot after smaller elements
    return i + 1                     // return pivot index
}

func main() {
    arr := []int{7, 2, 9, 4, 3}
    quickSort(arr, 0, len(arr)-1)
    fmt.Println(arr)
}

pi := partition(arr, low, high) // partition array and get pivot index

partition array around pivot to separate smaller and bigger elements

quickSort(arr, low, pi-1) // sort left part

recursively sort left sub-array before pivot

quickSort(arr, pi+1, high) // sort right part

recursively sort right sub-array after pivot

if arr[j] <= pivot { // if current element smaller or equal to pivot

check if element should go to left side of pivot

arr[i], arr[j] = arr[j], arr[i] // swap smaller element to front

move smaller element to correct position

arr[i+1], arr[high] = arr[high], arr[i+1] // place pivot after smaller elements

put pivot in its correct sorted position

Output

[2 3 4 7 9]

Complexity Analysis

Time: O(n log n) average case because the list is divided roughly in half each time and each element is compared once per level

Space: O(log n) due to recursive call stack depth in average case

vs Alternative: Better than simple sorting like bubble sort O(n^2) because it divides and conquers instead of comparing all pairs

Edge Cases

empty array

function returns immediately without changes

DSA Go

if low < high {

array with one element

function returns immediately as single element is sorted

DSA Go

if low < high {

array with all equal elements

partition keeps elements in place, recursion ends quickly

DSA Go

if arr[j] <= pivot {

When to Use This Pattern

When you see a problem asking to sort or order elements efficiently, especially with large data, reach for Quick Sort because it sorts by dividing the list around pivots quickly.

Common Mistakes

Mistake: Choosing pivot incorrectly or not swapping pivot to correct position
Fix: Always swap pivot to its correct place after partitioning to ensure correct division

Mistake: Not handling base case low >= high causing infinite recursion
Fix: Add condition to stop recursion when sub-array size is 0 or 1

Summary

Quick Sort sorts an array by dividing it around a pivot and sorting each part recursively.

Use Quick Sort when you need an efficient, general-purpose sorting algorithm.

The key insight is partitioning the array so smaller elements go left and bigger go right around the pivot.