Sorting series post 5 focuses on quicksort: average O(n log n), in-place, low constant factors, but it needs pivot strategy and tail recursion optimization to avoid worst-case O(n^2) and deep stacks. This is the ACERS view from theory to engineering practice.

Target Readers

  • Developers who want a production-ready quicksort.
  • Readers curious about pivot choice, duplicates handling, tail-recursion/hybrid strategies.
  • People who want to understand std::sort / Introsort design motivation.

Background and Motivation

  • Quicksort is often the default because it is in-place, cache-friendly, and fast, but worst-case O(n^2) and duplicates can hurt.
  • Engineering practice uses random pivot, median-of-three, three-way partition, tail recursion, and insertion for small segments.

A - Algorithm

Theme: Achieve average O(n log n) with in-place and low constants, while mitigating degeneration.

Basic example Array [3, 5, 2, 2, 8], pivot = 3:

  • After partition -> [2,2,3,5,8], left < 3, right >= 3.
  • Recurse on left and right segments.

C - Concepts

Key ConceptDescription
Pivot selectionRandom, median-of-three (first/mid/last), or median-of-five to reduce degeneration.
Partition strategyLomuto (single side) is simple but swaps more; Hoare (two-side) swaps less; three-way partition handles duplicates.
DuplicatesThree-way partition (<, =, >) prevents degeneration with many equal keys.
Tail recursionAlways recurse on smaller side and iterate on larger side to keep stack O(log n).
Hybrid strategyUse insertion for small segments; fall back to heap sort when recursion depth is too high (Introsort).

Complexity

  • Average time O(n log n), worst-case O(n^2) with extreme pivots.
  • Space: average recursion stack O(log n), worst-case O(n); tail recursion reduces risk.
  • Unstable, in-place.

E - Engineering

Scenario 1: General backend sorting (Go)

Background: dataset ~1e5, random distribution. Why: Go sort.Slice uses quick/heap hybrid; example includes insertion for small segments.

package main
import "fmt"

func insertion(a []int, l, r int) {
    for i := l+1; i <= r; i++ {
        key := a[i]; j := i-1
        for j >= l && a[j] > key { a[j+1]=a[j]; j-- }
        a[j+1]=key
    }
}

func partition(a []int, l, r int) int {
    pivot := a[(l+r)>>1]
    i, j := l, r
    for i <= j {
        for a[i] < pivot { i++ }
        for a[j] > pivot { j-- }
        if i <= j { a[i], a[j] = a[j], a[i]; i++; j-- }
    }
    return i
}

func quick(a []int, l, r int) {
    for r-l+1 > 16 {
        p := partition(a, l, r)
        if p-l < r-p { quick(a, l, p-1); l = p } else { quick(a, p, r); r = p-1 }
    }
    insertion(a, l, r)
}

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

Scenario 2: Many duplicates (Python three-way)

Background: many equal values (e.g., bucketed IDs), two-way partition degrades. Why: three-way partition handles equal keys in one pass.

def quick3(a, l=0, r=None):
    if r is None: r = len(a)-1
    while l < r:
        if r - l + 1 <= 16:
            for i in range(l+1, r+1):
                key=a[i]; j=i-1
                while j>=l and a[j]>key:
                    a[j+1]=a[j]; j-=1
                a[j+1]=key
            return
        pivot = a[(l+r)//2]
        lt, i, gt = l, l, r
        while i <= gt:
            if a[i] < pivot:
                a[lt], a[i] = a[i], a[lt]; lt+=1; i+=1
            elif a[i] > pivot:
                a[i], a[gt] = a[gt], a[i]; gt-=1
            else:
                i+=1
        if lt-l < r-gt: quick3(a, l, lt-1); l = gt+1
        else: quick3(a, gt+1, r); r = lt-1
    return a

arr=[3,5,2,2,8,1,7,2,2]
quick3(arr)
print(arr)

Scenario 3: C++ performance-sensitive partition (Hoare + median-of-three)

Background: performance-sensitive, need fewer swaps and more robust pivot.

#include <bits/stdc++.h>
using namespace std;

int median3(vector<int>& a, int l, int r){
    int m = l + (r-l)/2;
    if(a[m] < a[l]) swap(a[m], a[l]);
    if(a[r] < a[l]) swap(a[r], a[l]);
    if(a[m] < a[r]) swap(a[m], a[r]); // a[r] = median
    return a[r];
}

int partition(vector<int>& a, int l, int r){
    int pivot = median3(a,l,r);
    int i=l-1, j=r;
    while(true){
        do{ i++; } while(a[i] < pivot);
        do{ j--; } while(a[j] > pivot);
        if(i>=j) break;
        swap(a[i], a[j]);
    }
    swap(a[i], a[r]);
    return i;
}

void quick(vector<int>& a, int l, int r){
    while(l < r){
        if(r-l+1 <= 16){
            for(int i=l+1;i<=r;++i){int key=a[i], j=i-1; while(j>=l && a[j]>key){a[j+1]=a[j]; j--;} a[j+1]=key;}
            return;
        }
        int p = partition(a,l,r);
        if(p-l < r-p){ quick(a,l,p-1); l=p+1; }
        else{ quick(a,p+1,r); r=p-1; }
    }
}

Scenario 4: JavaScript small arrays with median-of-three

Background: mid-size arrays, use median-of-three + insertion threshold.

function insertion(a,l,r){
  for(let i=l+1;i<=r;i++){
    const key=a[i]; let j=i-1;
    while(j>=l && a[j]>key){ a[j+1]=a[j]; j--; }
    a[j+1]=key;
  }
}
function partition(a,l,r){
  const m = l + ((r-l)>>1);
  if(a[m]<a[l]) [a[m],a[l]]=[a[l],a[m]];
  if(a[r]<a[l]) [a[r],a[l]]=[a[l],a[r]];
  if(a[r]<a[m]) [a[r],a[m]]=[a[m],a[r]];
  const pivot = a[r];
  let i=l-1;
  for(let j=l;j<r;j++) if(a[j]<=pivot){ i++; [a[i],a[j]]=[a[j],a[i]]; }
  [a[i+1],a[r]]=[a[r],a[i+1]];
  return i+1;
}
function quick(a,l=0,r=a.length-1){
  while(l<r){
    if(r-l+1<=16){ insertion(a,l,r); return; }
    const p=partition(a,l,r);
    if(p-l < r-p){ quick(a,l,p-1); l=p+1; }
    else{ quick(a,p+1,r); r=p-1; }
  }
  return a;
}
console.log(quick([3,5,2,2,8,1,7]));

R - Reflection

  • Complexity: average O(n log n), worst O(n^2); stack depth O(log n) avg; tail recursion + insertion threshold keep it bounded.
  • Alternatives:
    • Need stability or guaranteed upper bound -> merge/heap/TimSort.
    • Known range -> counting/bucket/radix.
    • Standard libraries: C++ std::sort uses Introsort (quick + heap + insertion); Python/Java use TimSort (stable).
  • Why this works:
    • Random/median-of-three reduces degeneration.
    • Three-way partition handles duplicates.
    • Tail recursion + insertion threshold reduces stack depth and constants.

S - Summary

  • Quicksort strengths: in-place, low constants, cache-friendly, average O(n log n).
  • Risks: extreme pivot -> O(n^2); duplicates -> degeneration; unstable.
  • Robust strategy: random/median-of-three pivot, three-way partition, insertion for small segments, tail recursion; use Introsort ideas when needed.
  • Selection: stability/external -> merge/TimSort; memory tight + random -> quick/Introsort; duplicates -> three-way.

Practice Guide / Steps

  • Pivot: random or median-of-three; median-of-five for extra robustness.
  • Duplicates: use three-way partition; otherwise two-way is fine.
  • Set small segment threshold (e.g., 16/24) and insert; set depth limit to fall back to heap (Introsort).
  • Test sets: random, reverse, all equal, many duplicates, large arrays.

Common Pitfalls and Notes

  • Lomuto partition swaps more; Hoare partition returns an index that changes recursion boundaries.
  • Deep recursion can overflow stack: use tail recursion or iterative loops.
  • Not handling duplicates causes degeneration; three-way is critical.
  • Fixed first-element pivot degenerates on sorted data.

Runnable Examples: Minimal Multilang

Python (random pivot + three-way)

import random

def quick3(a, l=0, r=None):
    if r is None: r = len(a)-1
    while l < r:
        if r-l+1 <= 16:
            for i in range(l+1, r+1):
                key=a[i]; j=i-1
                while j>=l and a[j]>key:
                    a[j+1]=a[j]; j-=1
                a[j+1]=key
            return a
        pivot_i = random.randint(l, r)
        a[l], a[pivot_i] = a[pivot_i], a[l]
        pivot = a[l]
        lt, i, gt = l, l+1, r
        while i <= gt:
            if a[i] < pivot:
                a[lt], a[i] = a[i], a[lt]; lt+=1; i+=1
            elif a[i] > pivot:
                a[i], a[gt] = a[gt], a[i]; gt-=1
            else:
                i+=1
        if lt-l < r-gt: quick3(a, l, lt-1); l = gt+1
        else: quick3(a, gt+1, r); r = lt-1
    return a

arr=[3,5,2,2,8,1,7,2,2]
quick3(arr); print(arr)

C (Hoare partition + insertion threshold)

#include <stdlib.h>
void insertion(int *a,int l,int r){
    for(int i=l+1;i<=r;i++){
        int key=a[i], j=i-1;
        while(j>=l && a[j]>key){ a[j+1]=a[j]; j--; }
        a[j+1]=key;
    }
}
int partition(int *a,int l,int r){
    int pivot=a[(l+r)/2];
    int i=l-1, j=r+1;
    while(1){
        do{ i++; } while(a[i]<pivot);
        do{ j--; } while(a[j]>pivot);
        if(i>=j) return j;
        int t=a[i]; a[i]=a[j]; a[j]=t;
    }
}
void quick(int *a,int l,int r){
    while(l<r){
        if(r-l+1<=16){ insertion(a,l,r); return; }
        int p=partition(a,l,r);
        if(p-l < r-p){ quick(a,l,p); l=p+1; }
        else{ quick(a,p+1,r); r=p; }
    }
}

C++ (median-of-three + Hoare)

int partition(vector<int>& a,int l,int r){
    int m=l+(r-l)/2;
    if(a[m]<a[l]) swap(a[m],a[l]);
    if(a[r]<a[l]) swap(a[r],a[l]);
    if(a[r]<a[m]) swap(a[r],a[m]);
    int pivot=a[m];
    int i=l-1,j=r+1;
    while(true){
        do{i++;}while(a[i]<pivot);
        do{j--;}while(a[j]>pivot);
        if(i>=j) return j;
        swap(a[i],a[j]);
    }
}

Go (two-way, simplified)

func Quick(a []int, l, r int){
    for l<r {
        if r-l+1 <= 16 { insertion(a,l,r); return }
        p := partition(a,l,r)
        if p-l < r-p { Quick(a,l,p-1); l=p }
        else { Quick(a,p,r); r=p-1 }
    }
}

Rust (three-way)

pub fn quick3(a: &mut [i32]) {
    fn insertion(a: &mut [i32]) {
        for i in 1..a.len() {
            let key=a[i]; let mut j=i as i32-1;
            while j>=0 && a[j as usize]>key { a[(j+1) as usize]=a[j as usize]; j-=1; }
            a[(j+1) as usize]=key;
        }
    }
    fn sort(a: &mut [i32]) {
        let n=a.len();
        if n<=16 { insertion(a); return; }
        let pivot=a[n/2];
        let (mut lt, mut i, mut gt) = (0,0,n-1);
        while i<=gt {
            if a[i]<pivot { a.swap(lt,i); lt+=1; i+=1; }
            else if a[i]>pivot { a.swap(i,gt); if gt==0 {break;} gt-=1; }
            else { i+=1; }
        }
        sort(&mut a[..lt]);
        sort(&mut a[gt+1..]);
    }
    if !a.is_empty() { sort(a); }
}

JavaScript (median-of-three + insertion)

function insertion(a,l,r){
  for(let i=l+1;i<=r;i++){
    const key=a[i]; let j=i-1;
    while(j>=l && a[j]>key){ a[j+1]=a[j]; j--; }
    a[j+1]=key;
  }
}
function quick(a,l=0,r=a.length-1){
  while(l<r){
    if(r-l+1<=16){ insertion(a,l,r); return a; }
    const m=l+((r-l)>>1);
    if(a[m]<a[l]) [a[m],a[l]]=[a[l],a[m]];
    if(a[r]<a[l]) [a[r],a[l]]=[a[l],a[r]];
    if(a[r]<a[m]) [a[r],a[m]]=[a[m],a[r]];
    const pivot=a[m];
    let i=l, j=r;
    while(i<=j){
      while(a[i]<pivot) i++;
      while(a[j]>pivot) j--;
      if(i<=j){ [a[i],a[j]]=[a[j],a[i]]; i++; j--; }
    }
    if(j-l < r-i){ quick(a,l,j); l=i; }
    else { quick(a,i,r); r=j; }
  }
  return a;
}
console.log(quick([3,5,2,2,8,1,7]));

Best Practices

  • Default to language built-in sort; if custom, include random/median-of-three, three-way for duplicates, insertion threshold, tail recursion.
  • Use merge/TimSort for stability; consider Introsort for strict upper bounds.
  • Benchmark on random, reverse, all equal, many duplicates, and large arrays.

Conclusion

  • Quicksort is fast and in-place but must use pivot strategy and three-way partition to avoid degeneration.
  • Tail recursion + insertion thresholds are standard engineering practice; fall back to heap if depth grows (Introsort).
  • Selection rules: stability/external -> merge/TimSort; memory-tight random -> quick/Introsort; many duplicates -> three-way.

References and Further Reading

  • Hoare, “Quicksort” (1961)
  • Bentley & McIlroy, “Engineering a Sort Function” (1993)
  • C++ std::sort and std::stable_sort implementation notes

Meta

  • Reading time: approx. 16 min
  • SEO keywords: quicksort, pivot selection, three-way partition, tail recursion, Introsort
  • Meta description: sorting series (5) explaining pivot strategies, duplicate handling, tail recursion, and hybrid optimizations with multilingual implementations.

Call to Action (CTA)

  • Benchmark random vs fixed pivots on your real data; compare performance.
  • Add “insertion threshold + tail recursion” to your implementation and measure stack depth and time.
  • Follow the series: heap sort, non-comparison, TimSort/Introsort, selection guide.