Quick Sort as Divide and Conquer in DSA Go

Mental Model

Quick Sort splits the list into smaller parts around a pivot, sorts each part, and then combines them to get a sorted list.

Analogy: Imagine sorting a pile of cards by picking one card as a divider, putting smaller cards on one side and bigger cards on the other, then sorting each side separately before putting all cards back together.

Unsorted array:
[7, 2, 5, 3, 9]

Pivot chosen (e.g., 5):
[7, 2, 5, 3, 9]
 ↑pivot

Split into parts:
[2, 3] 5 [7, 9]

Sort parts separately and combine:
[2, 3, 5, 7, 9]

Dry Run Walkthrough

Input: array: [7, 2, 5, 3, 9]

Goal: Sort the array in ascending order using Quick Sort

Step 1: Choose pivot as last element 9; partition array around pivot

[7, 2, 5, 3, 9↑pivot]

Why: Pivot divides array into smaller and larger elements

Step 2: Partition: all elements less than 9 stay left; no swaps needed

[7, 2, 5, 3, 9]

Why: All elements are less than pivot, so pivot is at correct position

Step 3: Recursively quick sort left part [7, 2, 5, 3]

[7, 2, 5, 3]

Why: Sort left sub-array to fully sort array

Step 4: Choose pivot 3; partition around pivot

[7, 2, 5, 3↑pivot]

Why: Pivot divides sub-array

Step 5: Swap 7 and 2 because 2 < 3; array becomes [2, 7, 5, 3]

[2, 7, 5, 3]

Why: Place smaller elements left of pivot

Step 6: Swap pivot 3 with 7; array becomes [2, 3, 5, 7]

[2, 3, 5, 7]

Why: Pivot placed at correct position

Step 7: Recursively sort left [2] and right [5,7] parts; both are sorted

[2, 3, 5, 7]

Why: Base cases reached for recursion

Step 8: Combine sorted parts with pivot 9 at end

[2, 3, 5, 7, 9]

Why: Full array is now sorted

Result:

[2, 3, 5, 7, 9]

Annotated Code

DSA Go

package main

import "fmt"

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

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

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

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

partition array around pivot to separate smaller and larger elements

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

recursively sort left sub-array

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

recursively sort right sub-array

if arr[j] <= pivot { i++ arr[i], arr[j] = arr[j], arr[i] // swap smaller element to left }

move elements smaller than or equal to pivot to left side

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

put pivot in correct sorted position

Output

[2 3 5 7 9]

Complexity Analysis

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

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

vs Alternative: Compared to bubble sort's O(n^2), quick sort is much faster on average due to divide and conquer splitting

Edge Cases

empty array

function returns immediately without changes

DSA Go

if low < high {

array with one element

function returns immediately as array is already sorted

DSA Go

if low < high {

array with all equal elements

partition places pivot but no swaps needed; recursion ends quickly

DSA Go

if arr[j] <= pivot {

When to Use This Pattern

When you see a problem asking to sort or organize data efficiently, especially with divide and conquer hints, reach for Quick Sort because it splits and conquers the problem fast.

Common Mistakes

Mistake: Choosing pivot incorrectly or not placing pivot in correct position after partition
Fix: Always swap pivot to its correct place after partitioning smaller elements

Mistake: Not updating indices correctly during partition causing infinite recursion
Fix: Use separate pointers for smaller elements and current element to swap properly

Summary

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

Use Quick Sort when you want an efficient, average O(n log n) sorting algorithm.

The key insight is dividing the problem into smaller parts around a pivot and conquering each part separately.

Practice

1. What is the main idea behind the Quick Sort algorithm in the divide and conquer approach?

easy

A. Divide the array into smaller parts, sort them, and combine the results

B. Sort the array by repeatedly swapping adjacent elements

C. Use extra memory to merge two sorted arrays

D. Sort the array by selecting the smallest element each time

Solution

1. Step 1: Understand divide and conquer in Quick Sort

   Quick Sort divides the array into parts around a pivot, sorts parts recursively.

2. Step 2: Compare with other sorting methods

   Unlike bubble or selection sort, Quick Sort uses division and conquering subproblems.

3. Final Answer:

   Divide the array into smaller parts, sort them, and combine the results -> Option A

4. Quick Check:

   Divide and conquer = divide, sort, combine [OK]

Hint: Remember: divide, sort parts, then combine [OK]

Common Mistakes:

• Confusing Quick Sort with bubble or selection sort
• Thinking Quick Sort merges arrays like merge sort
• Ignoring the pivot selection step

2. Which of the following is the correct way to declare a partition function header in Go for Quick Sort?

easy

A. func partition(arr []int, low int, high int) int

B. func partition(arr int[], low int, high int) int

C. func partition(arr []int, low, high int) string

D. func partition(arr []int, low int, high int)

Solution

1. Step 1: Check Go syntax for function parameters

   In Go, slices are declared as []int, and multiple parameters can be declared with types.

2. Step 2: Verify return type for partition

   Partition returns an int index, so return type must be int.

3. Final Answer:

   func partition(arr []int, low int, high int) int -> Option A

4. Quick Check:

   Go func syntax with slice and int return = func partition(arr []int, low int, high int) int [OK]

Hint: Go slices use []type, return type must match function purpose [OK]

Common Mistakes:

• Using incorrect array syntax like int[]
• Wrong return type for partition function
• Missing return type in function declaration

3. What will be the output of the following Go code snippet after calling quickSort(arr, 0, len(arr)-1)?

func partition(arr []int, low, high int) int {
    pivot := arr[high]
    i := low - 1
    for j := low; j < high; j++ {
        if arr[j] < pivot {
            i++
            arr[i], arr[j] = arr[j], arr[i]
        }
    }
    arr[i+1], arr[high] = arr[high], arr[i+1]
    return i + 1
}

func quickSort(arr []int, low, high int) {
    if low < high {
        pi := partition(arr, low, high)
        quickSort(arr, low, pi-1)
        quickSort(arr, pi+1, high)
    }
}

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

medium

A. [7 4 2 1]

B. [4 2 7 1]

C. [1 2 4 7]

D. [1 4 2 7]

Solution

1. Step 1: Trace partition and quickSort on array [4, 2, 7, 1]

   Pivot is last element; after partition, smaller elements move left; recursive calls sort subarrays.

2. Step 2: Final sorted array after all recursive calls

   Array becomes [1, 2, 4, 7] after full quick sort completes.

3. Final Answer:

   [1 2 4 7] -> Option C

4. Quick Check:

   Quick Sort sorts array ascending = [1 2 4 7] [OK]

Hint: Quick Sort sorts in place; final array is sorted ascending [OK]

Common Mistakes:

• Assuming array stays unchanged
• Confusing pivot placement
• Ignoring recursive calls

4. Identify the bug in this Go Quick Sort partition function:

func partition(arr []int, low, high int) int {
    pivot := arr[high]
    i := low
    for j := low; j < high; j++ {
        if arr[j] < pivot {
            i++
            arr[i], arr[j] = arr[j], arr[i]
        }
    }
    arr[i+1], arr[high] = arr[high], arr[i+1]
    return i + 1
}

medium

A. Pivot should be arr[high], not arr[low]

B. Loop should start from low, not low + 1

C. Swap after loop should be arr[high], arr[i]

D. Variable i should be initialized to low - 1

Solution

1. Step 1: Analyze initialization of i in partition

   In standard Lomuto partition with pivot at arr[high], i should start at low - 1 to track smaller elements correctly.

2. Step 2: Check loop and swap logic

   Loop and swaps are correct if i starts at low - 1; current i = low causes incorrect partitioning.

3. Final Answer:

   Variable i should be initialized to low - 1 -> Option D

4. Quick Check:

   Correct i start fixes partition logic [OK]

Hint: Initialize i = low - 1 for Lomuto partition with pivot at end [OK]

Common Mistakes:

• Starting i at low causes wrong partition index
• Confusing pivot position with swap indices
• Changing pivot without adjusting i initialization

5. Given an array with many duplicate elements, which modification to Quick Sort helps improve performance and avoid worst-case behavior?

hard

A. Always choose the first element as pivot

B. Use a three-way partitioning to separate less, equal, and greater elements

C. Avoid recursion by using a single loop

D. Sort only the first half of the array

Solution

1. Step 1: Understand problem with duplicates in Quick Sort

   Duplicates cause many equal elements, leading to unbalanced partitions and slow sorting.

2. Step 2: Apply three-way partitioning solution

   Three-way partitioning divides array into less than, equal to, and greater than pivot, improving efficiency.

3. Final Answer:

   Use a three-way partitioning to separate less, equal, and greater elements -> Option B

4. Quick Check:

   Three-way partitioning handles duplicates better [OK]

Hint: Three-way partitioning handles duplicates efficiently [OK]

Common Mistakes:

• Choosing fixed pivot causes worst-case on duplicates
• Trying to avoid recursion breaks divide and conquer
• Sorting only half misses elements