Quick Sort

Overview

Quick Sort divides an array into smaller subarrays around a pivot element, recursively sorting each partition until the entire array is ordered. The algorithm selects a pivot, rearranges elements so that values less than the pivot come before it and values greater come after it, then recursively applies this process to the subarrays on either side of the pivot.

The algorithm was developed by Tony Hoare in 1959 and remains one of the most widely used sorting algorithms in practice. Despite having a worst-case time complexity of O(n²), Quick Sort achieves O(n log n) average-case performance and exhibits excellent cache locality, making it faster than many other sorting algorithms on typical data sets.

Quick Sort operates in-place, requiring only O(log n) additional space for the recursion stack. This space efficiency, combined with good average performance, makes it the default sorting algorithm in many standard libraries. The algorithm's performance depends heavily on pivot selection strategy and data characteristics.

def quick_sort(array)
  return array if array.length <= 1
  
  pivot = array[array.length / 2]
  left = array.select { |x| x < pivot }
  middle = array.select { |x| x == pivot }
  right = array.select { |x| x > pivot }
  
  quick_sort(left) + middle + quick_sort(right)
end

numbers = [3, 7, 8, 5, 2, 1, 9, 5, 4]
quick_sort(numbers)
# => [1, 2, 3, 4, 5, 5, 7, 8, 9]

Key Principles

Quick Sort operates on three fundamental principles: pivot selection, partitioning, and recursive division. Each principle affects the algorithm's performance and correctness.

Pivot Selection determines which element serves as the partition point. The pivot can be chosen as the first element, last element, middle element, random element, or median of a sample. Pivot choice directly impacts performance. Poor pivot selection on already-sorted data can degrade performance from O(n log n) to O(n²).

Partitioning rearranges array elements around the pivot. Elements less than the pivot move to the left partition, elements greater than the pivot move to the right partition, and the pivot ends up in its final sorted position. Various partition schemes exist, including Lomuto and Hoare partitioning, each with different performance characteristics and implementation complexity.

Recursive Division applies the sorting process to each partition. The algorithm recursively sorts the left and right subarrays until reaching base cases of arrays with zero or one element, which are already sorted. The recursion depth determines stack space usage and influences overall performance.

The partition operation maintains an invariant: after partitioning, all elements to the left of the pivot are less than or equal to it, and all elements to the right are greater than or equal to it. This invariant guarantees correctness because once the pivot is positioned, it never moves again.

def partition(array, low, high)
  pivot = array[high]
  i = low - 1
  
  (low...high).each do |j|
    if array[j] <= pivot
      i += 1
      array[i], array[j] = array[j], array[i]
    end
  end
  
  array[i + 1], array[high] = array[high], array[i + 1]
  i + 1
end

# Demonstrates partitioning around pivot
data = [10, 7, 8, 9, 1, 5]
pivot_index = partition(data, 0, data.length - 1)
# Array is now [1, 5, 7, 9, 10, 8] with pivot at index 2

The algorithm's efficiency derives from the balance of partition sizes. When partitions are roughly equal, the recursion tree has logarithmic depth. When partitions are highly unbalanced (one partition containing n-1 elements), the recursion tree has linear depth, resulting in quadratic time complexity.

Ruby Implementation

Ruby provides multiple approaches to implementing Quick Sort, from functional-style implementations using array methods to imperative in-place sorting. Each approach offers different trade-offs between readability, memory efficiency, and performance.

Functional Implementation uses Ruby's enumerable methods to create new arrays at each recursion level. This approach emphasizes clarity and immutability but creates multiple intermediate arrays.

def quick_sort_functional(array)
  return array if array.length <= 1
  
  pivot = array.sample
  less, equal, greater = array.partition { |x| x < pivot }
    .then { |less, rest| [less, rest.partition { |x| x == pivot }] }
    .then { |less, (equal, greater)| [less, equal, greater] }
  
  quick_sort_functional(less) + equal + quick_sort_functional(greater)
end

In-Place Implementation modifies the array directly, minimizing memory allocation. This approach matches the classical Quick Sort algorithm and provides better performance characteristics.

def quick_sort_inplace!(array, left = 0, right = array.length - 1)
  return array if left >= right
  
  pivot_index = partition!(array, left, right)
  quick_sort_inplace!(array, left, pivot_index - 1)
  quick_sort_inplace!(array, pivot_index + 1, right)
  
  array
end

def partition!(array, left, right)
  pivot = array[right]
  store_index = left
  
  (left...right).each do |i|
    if array[i] < pivot
      array[store_index], array[i] = array[i], array[store_index]
      store_index += 1
    end
  end
  
  array[store_index], array[right] = array[right], array[store_index]
  store_index
end

numbers = [64, 34, 25, 12, 22, 11, 90]
quick_sort_inplace!(numbers)
# => [11, 12, 22, 25, 34, 64, 90]

Three-Way Partitioning handles duplicate values efficiently by creating three partitions: less than pivot, equal to pivot, and greater than pivot. This optimization significantly improves performance on arrays with many duplicate values.

def quick_sort_3way!(array, left = 0, right = array.length - 1)
  return array if left >= right
  
  lt, gt = partition_3way!(array, left, right)
  quick_sort_3way!(array, left, lt - 1)
  quick_sort_3way!(array, gt + 1, right)
  
  array
end

def partition_3way!(array, left, right)
  pivot = array[left]
  lt = left
  gt = right
  i = left + 1
  
  while i <= gt
    if array[i] < pivot
      array[lt], array[i] = array[i], array[lt]
      lt += 1
      i += 1
    elsif array[i] > pivot
      array[i], array[gt] = array[gt], array[i]
      gt -= 1
    else
      i += 1
    end
  end
  
  [lt, gt]
end

data = [5, 2, 7, 2, 5, 2, 9, 5, 2, 5]
quick_sort_3way!(data)
# => [2, 2, 2, 2, 5, 5, 5, 5, 7, 9]

Randomized Pivot Selection reduces the probability of worst-case performance by selecting a random pivot. This approach provides O(n log n) expected time complexity regardless of input ordering.

def quick_sort_randomized!(array, left = 0, right = array.length - 1)
  return array if left >= right
  
  random_index = rand(left..right)
  array[right], array[random_index] = array[random_index], array[right]
  
  pivot_index = partition!(array, left, right)
  quick_sort_randomized!(array, left, pivot_index - 1)
  quick_sort_randomized!(array, pivot_index + 1, right)
  
  array
end

Hybrid Approach with Insertion Sort switches to insertion sort for small subarrays, reducing overhead from recursion and taking advantage of insertion sort's efficiency on small, nearly-sorted arrays.

def quick_sort_hybrid!(array, left = 0, right = array.length - 1)
  return array if left >= right
  
  if right - left < 10
    insertion_sort_range!(array, left, right)
  else
    pivot_index = partition!(array, left, right)
    quick_sort_hybrid!(array, left, pivot_index - 1)
    quick_sort_hybrid!(array, pivot_index + 1, right)
  end
  
  array
end

def insertion_sort_range!(array, left, right)
  (left + 1..right).each do |i|
    key = array[i]
    j = i - 1
    
    while j >= left && array[j] > key
      array[j + 1] = array[j]
      j -= 1
    end
    
    array[j + 1] = key
  end
  
  array
end

Performance Considerations

Quick Sort exhibits different performance characteristics depending on input data, pivot selection strategy, and implementation details. Understanding these factors enables informed decisions about when to use Quick Sort versus alternative sorting algorithms.

Time Complexity varies significantly based on partition balance. Best-case and average-case scenarios achieve O(n log n) when partitions are roughly equal. The algorithm performs approximately 1.39n log n comparisons on average for random data. Worst-case performance degrades to O(n²) when partitions are maximally unbalanced, occurring when the pivot is consistently the smallest or largest element.

The number of comparisons depends on the recursion tree depth. Balanced partitions create a tree of depth log n, with n work at each level, yielding O(n log n) total work. Unbalanced partitions create a tree of depth n, resulting in O(n²) comparisons.

Space Complexity for in-place implementations requires O(log n) auxiliary space for the recursion stack in the average case. Worst-case space complexity reaches O(n) when the recursion tree is completely unbalanced. Functional implementations that create new arrays at each level require O(n log n) space in the average case.

Stack depth directly correlates with space usage. Tail-call optimization or iterative implementations using explicit stacks can reduce space requirements. Sorting smaller partitions first before recursing on larger partitions guarantees O(log n) stack depth even in worst cases.

Cache Performance makes Quick Sort particularly effective on modern processors. The algorithm exhibits good spatial locality because it works on contiguous array sections. Partitioning operations access memory sequentially, maximizing cache hits. This cache efficiency often makes Quick Sort faster than merge sort in practice, despite similar theoretical complexity.

require 'benchmark'

def benchmark_quicksort(size)
  random_data = Array.new(size) { rand(1..10000) }
  sorted_data = (1..size).to_a
  reverse_data = (1..size).to_a.reverse
  
  Benchmark.bm(20) do |x|
    x.report("Random data:") do
      quick_sort_inplace!(random_data.dup)
    end
    
    x.report("Sorted data:") do
      quick_sort_inplace!(sorted_data.dup)
    end
    
    x.report("Reverse data:") do
      quick_sort_inplace!(reverse_data.dup)
    end
  end
end

benchmark_quicksort(10000)

Pivot Selection Impact dramatically affects performance. Fixed pivot strategies (first, last, or middle element) perform poorly on already-sorted or reverse-sorted data. Random pivot selection provides O(n log n) expected time for any input. Median-of-three pivot selection (choosing the median of first, middle, and last elements) combines good average performance with simpler implementation than full median finding.

Three-way partitioning improves performance on arrays with many duplicate values. Without three-way partitioning, duplicate values slow the algorithm because they do not reduce problem size effectively. With three-way partitioning, duplicates are handled in a single pass, providing O(n) performance when all elements are equal.

Optimization Techniques include switching to insertion sort for small subarrays (typically 5-15 elements), using iterative implementation to eliminate recursion overhead, employing sentinel values to eliminate boundary checks, and implementing tail recursion to sort the smaller partition first.

Practical Examples

Quick Sort applies to various real-world scenarios where in-place sorting with good average performance is required. These examples demonstrate different use cases and implementation variations.

Sorting Custom Objects requires defining comparison logic and maintaining stability when needed. Quick Sort is not stable by default but can be made stable with modifications.

class Student
  attr_accessor :name, :grade, :id
  
  def initialize(name, grade, id)
    @name = name
    @grade = grade
    @id = id
  end
  
  def <=>(other)
    grade <=> other.grade
  end
end

def quick_sort_objects!(array, left = 0, right = array.length - 1)
  return array if left >= right
  
  pivot_index = partition_objects!(array, left, right)
  quick_sort_objects!(array, left, pivot_index - 1)
  quick_sort_objects!(array, pivot_index + 1, right)
  
  array
end

def partition_objects!(array, left, right)
  pivot = array[right]
  store_index = left
  
  (left...right).each do |i|
    if array[i] < pivot
      array[store_index], array[i] = array[i], array[store_index]
      store_index += 1
    end
  end
  
  array[store_index], array[right] = array[right], array[store_index]
  store_index
end

students = [
  Student.new("Alice", 85, 1),
  Student.new("Bob", 92, 2),
  Student.new("Charlie", 78, 3),
  Student.new("David", 92, 4)
]

quick_sort_objects!(students)
# Sorts by grade, but relative order of Bob and David (both 92) is not preserved

Parallel Quick Sort divides work across multiple threads for large datasets. Each partition can be sorted independently once created, enabling parallel execution.

require 'concurrent'

def parallel_quick_sort(array, threshold = 1000)
  return quick_sort_functional(array) if array.length < threshold
  
  pivot = array[array.length / 2]
  less = array.select { |x| x < pivot }
  equal = array.select { |x| x == pivot }
  greater = array.select { |x| x > pivot }
  
  futures = [
    Concurrent::Future.execute { parallel_quick_sort(less, threshold) },
    Concurrent::Future.execute { parallel_quick_sort(greater, threshold) }
  ]
  
  futures[0].value + equal + futures[1].value
end

large_array = Array.new(100000) { rand(1..1000000) }
sorted = parallel_quick_sort(large_array)

K-th Element Selection uses Quick Sort partitioning to find the k-th smallest element without fully sorting the array. This approach achieves O(n) average-case performance.

def quick_select(array, k, left = 0, right = array.length - 1)
  return array[left] if left == right
  
  pivot_index = partition!(array, left, right)
  
  if k == pivot_index
    array[k]
  elsif k < pivot_index
    quick_select(array, k, left, pivot_index - 1)
  else
    quick_select(array, k, pivot_index + 1, right)
  end
end

def find_median(array)
  quick_select(array.dup, array.length / 2)
end

numbers = [7, 10, 4, 3, 20, 15]
median = find_median(numbers)
# => 7 (the 3rd smallest element in 0-indexed array)

Sorting With Custom Comparator enables sorting based on complex criteria or multiple fields.

def quick_sort_with_comparator!(array, comparator, left = 0, right = array.length - 1)
  return array if left >= right
  
  pivot_index = partition_with_comparator!(array, comparator, left, right)
  quick_sort_with_comparator!(array, comparator, left, pivot_index - 1)
  quick_sort_with_comparator!(array, comparator, pivot_index + 1, right)
  
  array
end

def partition_with_comparator!(array, comparator, left, right)
  pivot = array[right]
  store_index = left
  
  (left...right).each do |i|
    if comparator.call(array[i], pivot) < 0
      array[store_index], array[i] = array[i], array[store_index]
      store_index += 1
    end
  end
  
  array[store_index], array[right] = array[right], array[store_index]
  store_index
end

# Sort strings by length, then alphabetically
strings = ["apple", "pie", "banana", "cat", "dog"]
comparator = ->(a, b) do
  length_cmp = a.length <=> b.length
  length_cmp.zero? ? a <=> b : length_cmp
end

quick_sort_with_comparator!(strings, comparator)
# => ["cat", "dog", "pie", "apple", "banana"]

Common Patterns

Quick Sort implementations follow established patterns that address different requirements and optimize performance. Recognizing these patterns enables selecting the appropriate variation for specific use cases.

Lomuto Partition Scheme places the pivot at the end and maintains a boundary between elements less than the pivot and elements greater than or equal to the pivot. This scheme is simpler to implement but performs more swaps than Hoare partitioning.

def lomuto_partition(array, low, high)
  pivot = array[high]
  i = low - 1
  
  (low...high).each do |j|
    if array[j] < pivot
      i += 1
      array[i], array[j] = array[j], array[i]
    end
  end
  
  array[i + 1], array[high] = array[high], array[i + 1]
  i + 1
end

Hoare Partition Scheme uses two pointers that move toward each other, swapping elements when they find values on the wrong side of the pivot. This scheme performs fewer swaps on average but is more complex to implement correctly.

def hoare_partition(array, low, high)
  pivot = array[(low + high) / 2]
  i = low - 1
  j = high + 1
  
  loop do
    i += 1 while array[i] < pivot
    j -= 1 while array[j] > pivot
    
    return j if i >= j
    
    array[i], array[j] = array[j], array[i]
  end
end

def quick_sort_hoare!(array, low = 0, high = array.length - 1)
  return array if low >= high
  
  p = hoare_partition(array, low, high)
  quick_sort_hoare!(array, low, p)
  quick_sort_hoare!(array, p + 1, high)
  
  array
end

Dual-Pivot Quick Sort uses two pivots to divide the array into three partitions. This pattern reduces the number of comparisons and is used in Java's sorting implementation for primitive arrays.

def dual_pivot_quick_sort!(array, left = 0, right = array.length - 1)
  return array if left >= right
  
  if array[left] > array[right]
    array[left], array[right] = array[right], array[left]
  end
  
  pivot1 = array[left]
  pivot2 = array[right]
  
  i = left + 1
  lt = left + 1
  gt = right - 1
  
  while i <= gt
    if array[i] < pivot1
      array[i], array[lt] = array[lt], array[i]
      lt += 1
    elsif array[i] > pivot2
      array[i], array[gt] = array[gt], array[i]
      gt -= 1
      i -= 1
    end
    i += 1
  end
  
  lt -= 1
  gt += 1
  
  array[left], array[lt] = array[lt], array[left]
  array[right], array[gt] = array[gt], array[right]
  
  dual_pivot_quick_sort!(array, left, lt - 1)
  dual_pivot_quick_sort!(array, lt + 1, gt - 1)
  dual_pivot_quick_sort!(array, gt + 1, right)
  
  array
end

Tail Recursion Optimization eliminates recursion on one partition by converting it to iteration, reducing stack space to O(log n) guaranteed.

def quick_sort_tail_recursive!(array, left = 0, right = array.length - 1)
  while left < right
    pivot_index = partition!(array, left, right)
    
    if pivot_index - left < right - pivot_index
      quick_sort_tail_recursive!(array, left, pivot_index - 1)
      left = pivot_index + 1
    else
      quick_sort_tail_recursive!(array, pivot_index + 1, right)
      right = pivot_index - 1
    end
  end
  
  array
end

Introspective Sort Pattern monitors recursion depth and switches to heapsort if depth exceeds a threshold, guaranteeing O(n log n) worst-case performance while maintaining Quick Sort's average-case speed.

def introsort!(array, left = 0, right = array.length - 1, depth_limit = nil)
  depth_limit ||= (Math.log2(array.length) * 2).floor
  
  return array if left >= right
  
  if depth_limit == 0
    heap_sort_range!(array, left, right)
  else
    pivot_index = partition!(array, left, right)
    introsort!(array, left, pivot_index - 1, depth_limit - 1)
    introsort!(array, pivot_index + 1, right, depth_limit - 1)
  end
  
  array
end

Common Pitfalls

Quick Sort implementations encounter specific problems that degrade performance or cause incorrect behavior. Understanding these pitfalls prevents subtle bugs and performance issues.

Quadratic Performance on Sorted Data occurs when using fixed pivot strategies (first or last element) on already-sorted or reverse-sorted arrays. Each partition contains n-1 elements, resulting in O(n²) time complexity.

# Poor implementation - degrades on sorted data
def bad_quick_sort(array)
  return array if array.length <= 1
  
  pivot = array[0]  # Always using first element as pivot
  left = array[1..-1].select { |x| x < pivot }
  right = array[1..-1].select { |x| x >= pivot }
  
  bad_quick_sort(left) + [pivot] + bad_quick_sort(right)
end

# Degrades to O(n²) on sorted data
sorted = (1..1000).to_a
bad_quick_sort(sorted)  # Very slow

Stack Overflow happens when sorting large arrays with naive recursive implementations. The recursion depth can reach O(n) in worst cases, exhausting stack space.

# Vulnerable to stack overflow
def naive_quick_sort!(array, left = 0, right = array.length - 1)
  return if left >= right
  
  pivot = partition!(array, left, right)
  naive_quick_sort!(array, left, pivot - 1)  # May recurse deeply
  naive_quick_sort!(array, pivot + 1, right)  # May recurse deeply
end

# Stack overflow on adversarial input
adversarial = (1..100000).to_a.reverse
naive_quick_sort!(adversarial)  # SystemStackError

Incorrect Partition Boundary Handling causes infinite recursion or skips elements when partition indices are wrong. Off-by-one errors in partition logic are particularly common.

# Incorrect - can cause infinite recursion
def broken_partition(array, low, high)
  pivot = array[high]
  i = low
  
  (low..high).each do |j|  # Should be (low...high)
    if array[j] < pivot
      array[i], array[j] = array[j], array[i]
      i += 1
    end
  end
  
  array[i], array[high] = array[high], array[i]
  i  # Returns wrong index when pivot is smallest element
end

Duplicate Handling Inefficiency slows sorting when many duplicate values exist. Standard two-way partitioning does not group duplicates, causing unnecessary recursive calls on equal elements.

# Inefficient on duplicates
def poor_duplicate_handling(array)
  return array if array.length <= 1
  
  pivot = array[0]
  left = array[1..-1].select { |x| x < pivot }
  right = array[1..-1].select { |x| x >= pivot }  # Includes duplicates
  
  poor_duplicate_handling(left) + [pivot] + poor_duplicate_handling(right)
end

# Slow on many duplicates
duplicates = Array.new(10000) { rand(1..10) }
poor_duplicate_handling(duplicates)  # Unnecessarily slow

Mutation of Input During Comparison causes unpredictable behavior if comparison operations modify array elements or if pivot references become invalid.

# Dangerous - comparing mutable objects
class MutableScore
  attr_accessor :value
  
  def initialize(value)
    @value = value
  end
  
  def <=>(other)
    self.value += 1  # Modifies during comparison - DO NOT DO THIS
    self.value <=> other.value
  end
end

scores = Array.new(100) { MutableScore.new(rand(1..100)) }
quick_sort_objects!(scores)  # Produces incorrect results

Not Handling Empty or Single-Element Edge Cases leads to errors when recursion does not properly check base cases.

# Missing edge case handling
def unsafe_quick_sort(array, left, right)
  pivot_index = partition!(array, left, right)
  unsafe_quick_sort(array, left, pivot_index - 1)  # Fails if left > pivot_index - 1
  unsafe_quick_sort(array, pivot_index + 1, right)  # Fails if pivot_index + 1 > right
end

Random Pivot Not Actually Random occurs when using pseudo-random number generators without proper seeding, causing predictable patterns that an attacker could exploit to force worst-case behavior.

# Predictable random - vulnerable to attack
def predictable_pivot_sort!(array, left = 0, right = array.length - 1)
  Random.srand(42)  # Don't reset seed in recursive function
  return array if left >= right
  
  random_index = rand(left..right)
  array[right], array[random_index] = array[random_index], array[right]
  
  pivot_index = partition!(array, left, right)
  predictable_pivot_sort!(array, left, pivot_index - 1)
  predictable_pivot_sort!(array, pivot_index + 1, right)
  
  array
end

Reference

Algorithm Complexity

Partition Schemes

Pivot Selection Strategies

Optimization Techniques

Common Implementation Patterns

Ruby Standard Library