Quick Sort

Quick Sort is a highly efficient, comparison-based sorting algorithm that uses the Divide and Conquer strategy. 

It works by selecting a pivot element and partitioning the array so that all elements smaller than the pivot go to its left, and all elements greater go to its right. The same process is then applied recursively to the left and right sub-arrays.

Quick Sort is one of the fastest general-purpose sorting algorithms in practice and is widely used in real-world libraries and systems.

How Quick Sort Works?

1. Choose a pivot element from the array (commonly the last element, first element, or a random element).
2. Partition the array: rearrange elements so that everything smaller than the pivot is on its left and everything larger is on its right. The pivot now sits in its final sorted position.
3. Recursively apply steps 1 and 2 to the sub-array on the left of the pivot.
4. Recursively apply steps 1 and 2 to the sub-array on the right of the pivot.
5. The recursion ends when a sub-array has 0 or 1 elements (already sorted).

Example: Sorting [10, 80, 30, 90, 40, 50, 70]

Initial array: [10, 80, 30, 90, 40, 50, 70], pivot = 70

Partitioning around pivot 70:

• Compare each element with 70, moving smaller ones to the left section.
• 10 < 70 → keep in left section
• 80 > 70 → stays right
• 30 < 70 → moves to left section
• 90 > 70 → stays right
• 40 < 70 → moves to left section
• 50 < 70 → moves to left section
• After partitioning, pivot 70 lands in its correct position: [10, 30, 40, 50, 70, 90, 80] (Pivot 70 is now at index 4 — its final sorted position)

Recursively sort left sub-array [10, 30, 40, 50] (pivot = 50)

• All elements are already less than 50 → [10, 30, 40, 50], pivot fixed at last position.
• Continue recursively on [10, 30, 40] (pivot = 40) → sorted as [10, 30, 40]
• Continue on [10, 30] (pivot = 30) → sorted as [10, 30]

Recursively sort right sub-array [90, 80] (pivot = 80)

• 90 > 80 → stays right → [80, 90]

Final Sorted Array: [10, 30, 40, 50, 70, 80, 90]

Visual Walkthrough of the First Partition Step

Here's the same first partition shown visually, tracking two pointers i (boundary of the "smaller than pivot" section) and j (scanning pointer) as they move through the array with pivot = 70.

Array:   [ 10,  80,  30,  90,  40,  50,  70 ]
Index:      0    1    2    3    4    5    6  (pivot at index 6)
 i = -1 (nothing placed in "smaller" section yet)
 j=0 → 10 < 70 → i becomes 0, swap a[i] & a[j] (no change, same spot)
      [ 10,  80,  30,  90,  40,  50,  70 ]   i=0
 j=1 → 80 > 70 → skip
      [ 10,  80,  30,  90,  40,  50,  70 ]   i=0
 j=2 → 30 < 70 → i becomes 1, swap a[1] & a[2]
      [ 10,  30,  80,  90,  40,  50,  70 ]   i=1
 j=3 → 90 > 70 → skip
      [ 10,  30,  80,  90,  40,  50,  70 ]   i=1
 j=4 → 40 < 70 → i becomes 2, swap a[2] & a[4]
      [ 10,  30,  40,  90,  80,  50,  70 ]   i=2
 j=5 → 50 < 70 → i becomes 3, swap a[3] & a[5]
      [ 10,  30,  40,  50,  80,  90,  70 ]   i=3
 End of scan → swap pivot a[6] with a[i+1] = a[4]
      [ 10,  30,  40,  50,  70,  90,  80 ]
 Pivot 70 is now locked in its final sorted position (index 4).

Recursion Tree

Quick Sort's Divide and Conquer nature is easiest to see as a tree. Each node splits into a left call (elements smaller than pivot) and a right call (elements larger than pivot):

                         [10,80,30,90,40,50,70]
                                 pivot=70
                        /                       \
              [10,30,40,50]                   [90,80]
                pivot=50                       pivot=80
               /                                    \
        [10,30,40]                                [90]
         pivot=40                                (base case)
        /
   [10,30]
   pivot=30
   /
 [10]
(base case)

Each level of this tree represents one "round" of partitioning across the array. When the pivot splits the array roughly in half each time (as in a balanced tree above), the tree has about log n levels, and each level does O(n) total work across all its partitions which is exactly where the O(n log n) average-case time complexity comes from. 

If the pivot is consistently the smallest or largest element, the tree becomes a lopsided chain of n levels instead this is what produces the O(n²) worst case.

Pseudocode of Quick Sort

Step 1: Start
Step 2: Function quickSort(array, low, high):
Step 3:     If low < high:
Step 4:         pivotIndex = partition(array, low, high)
Step 5:         quickSort(array, low, pivotIndex - 1)
Step 6:         quickSort(array, pivotIndex + 1, high)

Step 7: Function partition(array, low, high):
Step 8:     pivot = array[high]
Step 9:     i = low - 1
Step 10:    For j = low to high - 1:
                If array[j] < pivot:
                    i = i + 1
                    Swap array[i] and array[j]
Step 11:    Swap array[i+1] and array[high]
Step 12:    Return i + 1
Step 13: End

Where Quick Sort Is Used in the Real World?

• Many standard library sort functions use a variant of Quick Sort. For example, C's standard library qsort() function is named directly after it, and Java's Arrays.sort() for primitive types historically used a Dual-Pivot Quick Sort variant for better average-case performance.
• Quick Sort's in-place, cache-friendly behavior makes it a common default choice in performance-critical systems where average-case speed and low memory overhead both matter more than guaranteed worst-case behavior.
• It's frequently combined with other algorithms in production-grade "introspective sort" (IntroSort) implementations, which start with Quick Sort but switch to Heap Sort if the recursion gets too deep protecting against the O(n²) worst case while keeping Quick Sort's average-case speed.

Advantages

• Very fast in practice average case O(n log n), often beats other O(n log n) algorithms due to low constant factors and good cache performance.
• In-place sorting needs very little extra memory compared to Merge Sort.
• Works well with large datasets.
• Easily parallelizable (left and right partitions can be sorted independently).

Disadvantages

• Worst-case time complexity is O(n²), which happens with a poor pivot choice (e.g., already sorted array with last-element pivot).
• Not stable the relative order of equal elements may change.
• Recursive nature means it uses call-stack space; worst case stack depth is O(n).
• Performance heavily depends on pivot selection strategy.

Time and Space Complexity

Space Complexity: O(log n) on average (due to recursion stack for balanced partitions); O(n) in the worst case (highly unbalanced recursion).

Stability: Not stable In-place: Yes

How Quick Sort Compares to Other Sorts?

* Depends on gap sequence used.

When to Use Quick Sort?

• Large datasets where average-case speed matters most.
• When memory usage needs to stay low (compared to Merge Sort).
• General-purpose sorting where worst-case behavior can be mitigated (e.g., using randomized pivot or median-of-three pivot selection).

Practice Questions (Solve on your own)

1. Sort the array [45, 12, 89, 3, 67, 22] using Quick Sort, choosing the last element as the pivot at every step, and show each partition.
2. Trace Quick Sort on the array [1, 2, 3, 4, 5] using the last element as pivot. What is the resulting time complexity for this case, and why?
3. For the array [38, 27, 43, 3, 9, 82, 10], identify the position where the first pivot lands after the first partition step.
4. Explain, with an example array, why Quick Sort is considered "not stable."
5. Modify the partition scheme to choose the first element as pivot instead of the last, and rewrite the pseudocode.
6. For the array [9, 5, 1, 4, 3], count the total number of comparisons made using last-element pivot selection.
7. Describe a real-world scenario where Quick Sort's worst-case O(n²) behavior could occur, and suggest one way to avoid it.
8. Write a program implementing Quick Sort using recursion, and test it on an array of 10 random integers.
9. Compare the space complexity of Quick Sort and Merge Sort. Which one is more memory-efficient and why?
10. Given the array [8, 3, 7, 4, 9, 8, 1], manually sort it using Quick Sort and list the pivot chosen at each recursive call.