Stable Quicksort — VisualAlgorithms Docs

How it works

Quicksort that preserves the order of equal elements by partitioning each range into less / equal / greater buffers and writing them straight back, so every level visibly regroups the bars in place. The equal block lands in its final position immediately.
Implementation

      
 function stableQuickSort(arr, stats) {
  const n = arr.length;
  if (n < 2) {
    if (n === 1) markSorted(0);
    return;
  }
  const INSERTION_THRESHOLD = 24;
  const metrics = stats.educational.metrics;
  const recordMetric = (name, delta = 1) => {
    metrics[name] = (metrics[name] || 0) + delta;
  };
  metrics.insertionThreshold = INSERTION_THRESHOLD;
  function insertionSort(lo, hi) {
    recordMetric('insertionSortCalls');
    for (let i = lo + 1; i < hi; i++) {
      const value = arr[i];
      let j = i;
      while (j > lo) {
        compare(j - 1, i);
        if (arr[j - 1] <= value) break;
        arr[j] = arr[j - 1];
        write(j, arr[j]);
        j--;
      }
      arr[j] = value;
      write(j, value);
    }
    for (let i = lo; i < hi; i++) markSorted(i);
  }
  function medianOfThree(lo, mid, hi) {
    compare(lo, mid);
    compare(mid, hi);
    compare(lo, hi);
    recordMetric('pivotSelections');
    let a = arr[lo];
    let b = arr[mid];
    let c = arr[hi];
    if (a > b) {
      const t = a;
      a = b;
      b = t;
    }
    if (b > c) {
      const t = b;
      b = c;
      c = t;
    }
    if (a > b) {
      const t = a;
      a = b;
      b = t;
    }
    return b;
  }
  function sort(lo, hi) {
    const len = hi - lo;
    if (len <= 1) {
      if (len === 1) markSorted(lo);
      return;
    }
    if (len <= INSERTION_THRESHOLD) {
      insertionSort(lo, hi);
      return;
    }
    const mid = lo + (len >> 1);
    const pivot = medianOfThree(lo, mid, hi - 1);
    recordMetric('stablePartitions');
    const less = [];
    const equal = [];
    const greater = [];
    for (let i = lo; i < hi; i++) {
      compare(i, mid);
      const value = arr[i];
      if (value < pivot) less.push(value); else if (value > pivot) greater.push(value); else equal.push(value);
    }
    recordMetric('bufferedItems', len);
    let w = lo;
    for (let i = 0; i < less.length; i++) {
      arr[w] = less[i];
      write(w, less[i]);
      w++;
    }
    const eqStart = w;
    for (let i = 0; i < equal.length; i++) {
      arr[w] = equal[i];
      write(w, equal[i]);
      markSorted(w);
      w++;
    }
    const gtStart = w;
    for (let i = 0; i < greater.length; i++) {
      arr[w] = greater[i];
      write(w, greater[i]);
      w++;
    }
    checkpoint(eqStart, n);
    sort(lo, eqStart);
    sort(gtStart, hi);
  }
  sort(0, n);
  checkpoint(n, n);
}
 def stableQuickSort(arr, stats):
    def recordMetric(name, ):
        metrics[name] = ((metrics[name] or 0) + delta)

    def insertionSort(lo, hi):
        recordMetric("insertionSortCalls")
        for i in range((lo + 1), hi):
            value = arr[i]
            j = i
            while (j > lo):
                compare((j - 1), i)
                if (arr[(j - 1)] <= value):
                    break
                arr[j] = arr[(j - 1)]
                write(j, arr[j])
                j -= 1
            arr[j] = value
            write(j, value)
        for i in range(lo, hi):
            markSorted(i)

    def medianOfThree(lo, mid, hi):
        compare(lo, mid)
        compare(mid, hi)
        compare(lo, hi)
        recordMetric("pivotSelections")
        a = arr[lo]
        b = arr[mid]
        c = arr[hi]
        if (a > b):
            t = a
            a = b
            b = t
        if (b > c):
            t = b
            b = c
            c = t
        if (a > b):
            t = a
            a = b
            b = t
        return b

    def sort(lo, hi):
        len = (hi - lo)
        if (len <= 1):
            if (len == 1):
                markSorted(lo)
            return
        if (len <= INSERTION_THRESHOLD):
            insertionSort(lo, hi)
            return
        mid = (lo + (len >> 1))
        pivot = medianOfThree(lo, mid, (hi - 1))
        recordMetric("stablePartitions")
        less = []
        equal = []
        greater = []
        for i in range(lo, hi):
            compare(i, mid)
            value = arr[i]
            if (value < pivot):
                less.append(value)
            elif (value > pivot):
                greater.append(value)
            else:
                equal.append(value)
        recordMetric("bufferedItems", len)
        w = lo
        for i in range(len(less)):
            arr[w] = less[i]
            write(w, less[i])
            w += 1
        eqStart = w
        for i in range(len(equal)):
            arr[w] = equal[i]
            write(w, equal[i])
            markSorted(w)
            w += 1
        gtStart = w
        for i in range(len(greater)):
            arr[w] = greater[i]
            write(w, greater[i])
            w += 1
        checkpoint(eqStart, n)
        sort(lo, eqStart)
        sort(gtStart, hi)

    if (n < 2):
        if (n == 1):
            markSorted(0)
        return
    INSERTION_THRESHOLD = 24
    metrics.insertionThreshold = INSERTION_THRESHOLD
    sort(0, n)
    checkpoint(n, n)
 #include <vector>
#include <algorithm>
void recordMetric(int name, int );
void insertionSort(int lo, int hi);
int medianOfThree(int lo, int mid, int hi);
void sort(int lo, int hi);

void recordMetric(int name, int ) {
    metrics[name] = (((metrics[name]) != 0 ? (metrics[name]) : (0)) + delta);
}

void insertionSort(int lo, int hi) {
    recordMetric("insertionSortCalls");
    for(int i=(lo + 1); i<hi; i++) {
        int value = arr[i];
        int j = i;
        while((j > lo)) {
            compare((j - 1), i);
            if((arr[(j - 1)] <= value)) {
                break;
            }
            arr[j] = arr[(j - 1)];
            write(j, arr[j]);
            j--;
        }
        arr[j] = value;
        write(j, value);
    }
    for(int i=lo; i<hi; i++) {
        markSorted(i);
    }
}

int medianOfThree(int lo, int mid, int hi) {
    compare(lo, mid);
    compare(mid, hi);
    compare(lo, hi);
    recordMetric("pivotSelections");
    int a = arr[lo];
    int b = arr[mid];
    int c = arr[hi];
    if((a > b)) {
        int t = a;
        a = b;
        b = t;
    }
    if((b > c)) {
        int t = b;
        b = c;
        c = t;
    }
    if((a > b)) {
        int t = a;
        a = b;
        b = t;
    }
    return b;
}

void sort(int lo, int hi) {
    int len = (hi - lo);
    if((len <= 1)) {
        if((len == 1)) {
            markSorted(lo);
        }
        return;
    }
    if((len <= INSERTION_THRESHOLD)) {
        insertionSort(lo, hi);
        return;
    }
    int mid = (lo + (len >> 1));
    int pivot = medianOfThree(lo, mid, (hi - 1));
    recordMetric("stablePartitions");
    std::vector<int> less;
    std::vector<int> equal;
    std::vector<int> greater;
    for(int i=lo; i<hi; i++) {
        compare(i, mid);
        int value = arr[i];
        if((value < pivot)) {
            less.push_back(value);
        } else if((value > pivot)) {
            greater.push_back(value);
        } else {
            equal.push_back(value);
        }
    }
    recordMetric("bufferedItems", len);
    int w = lo;
    for(int i=0; i<(int)less.size(); i++) {
        arr[w] = less[i];
        write(w, less[i]);
        w++;
    }
    int eqStart = w;
    for(int i=0; i<(int)equal.size(); i++) {
        arr[w] = equal[i];
        write(w, equal[i]);
        markSorted(w);
        w++;
    }
    int gtStart = w;
    for(int i=0; i<(int)greater.size(); i++) {
        arr[w] = greater[i];
        write(w, greater[i]);
        w++;
    }
    checkpoint(eqStart, n);
    sort(lo, eqStart);
    sort(gtStart, hi);
}

void sort(std::vector<int>& arr, int n, int& comparisons, int& swaps) {
    if((n < 2)) {
        if((n == 1)) {
            markSorted(0);
        }
        return;
    }
    int INSERTION_THRESHOLD = 24;
    int metrics = educational.metrics;
    metrics.insertionThreshold = INSERTION_THRESHOLD;
    sort(0, n);
    checkpoint(n, n);
} void recordMetric(int name, int ) {
    metrics[name] = (((metrics[name]) != 0 ? (metrics[name]) : (0)) + delta);
}

void insertionSort(int lo, int hi) {
    recordMetric("insertionSortCalls");
    for(int i=(lo + 1); i<hi; i++) {
        int value = arr[i];
        int j = i;
        while((j > lo)) {
            compare((j - 1), i);
            if((arr[(j - 1)] <= value)) {
                break;
            }
            arr[j] = arr[(j - 1)];
            write(j, arr[j]);
            j--;
        }
        arr[j] = value;
        write(j, value);
    }
    for(int i=lo; i<hi; i++) {
        markSorted(i);
    }
}

int medianOfThree(int lo, int mid, int hi) {
    compare(lo, mid);
    compare(mid, hi);
    compare(lo, hi);
    recordMetric("pivotSelections");
    int a = arr[lo];
    int b = arr[mid];
    int c = arr[hi];
    if((a > b)) {
        int t = a;
        a = b;
        b = t;
    }
    if((b > c)) {
        int t = b;
        b = c;
        c = t;
    }
    if((a > b)) {
        int t = a;
        a = b;
        b = t;
    }
    return b;
}

void sort(int lo, int hi) {
    int len = (hi - lo);
    if((len <= 1)) {
        if((len == 1)) {
            markSorted(lo);
        }
        return;
    }
    if((len <= INSERTION_THRESHOLD)) {
        insertionSort(lo, hi);
        return;
    }
    int mid = (lo + (len >> 1));
    int pivot = medianOfThree(lo, mid, (hi - 1));
    recordMetric("stablePartitions");
    var less = new List<int>();
    var equal = new List<int>();
    var greater = new List<int>();
    for(int i=lo; i<hi; i++) {
        compare(i, mid);
        int value = arr[i];
        if((value < pivot)) {
            less.Add(value);
        } else if((value > pivot)) {
            greater.Add(value);
        } else {
            equal.Add(value);
        }
    }
    recordMetric("bufferedItems", len);
    int w = lo;
    for(int i=0; i<less.Count; i++) {
        arr[w] = less[i];
        write(w, less[i]);
        w++;
    }
    int eqStart = w;
    for(int i=0; i<equal.Count; i++) {
        arr[w] = equal[i];
        write(w, equal[i]);
        markSorted(w);
        w++;
    }
    int gtStart = w;
    for(int i=0; i<greater.Count; i++) {
        arr[w] = greater[i];
        write(w, greater[i]);
        w++;
    }
    checkpoint(eqStart, n);
    sort(lo, eqStart);
    sort(gtStart, hi);
}

public void Sort(int[] arr, int n, dynamic stats) {
    if((n < 2)) {
        if((n == 1)) {
            markSorted(0);
        }
        return;
    }
    int INSERTION_THRESHOLD = 24;
    int metrics = stats.educational.metrics;
    metrics.insertionThreshold = INSERTION_THRESHOLD;
    sort(0, n);
    checkpoint(n, n);
} #include <stdio.h>
#include <stdlib.h>
void recordMetric(int name, int );
void insertionSort(int lo, int hi);
int medianOfThree(int lo, int mid, int hi);
void sort(int lo, int hi);

void recordMetric(int name, int ) {
    metrics[name] = (((metrics[name]) != 0 ? (metrics[name]) : (0)) + delta);
}

void insertionSort(int lo, int hi) {
    recordMetric("insertionSortCalls");
    for(int i=(lo + 1); i<hi; i++) {
        int value = arr[i];
        int j = i;
        while((j > lo)) {
            compare((j - 1), i);
            if((arr[(j - 1)] <= value)) {
                break;
            }
            arr[j] = arr[(j - 1)];
            write(j, arr[j]);
            j--;
        }
        arr[j] = value;
        write(j, value);
    }
    for(int i=lo; i<hi; i++) {
        markSorted(i);
    }
}

int medianOfThree(int lo, int mid, int hi) {
    compare(lo, mid);
    compare(mid, hi);
    compare(lo, hi);
    recordMetric("pivotSelections");
    int a = arr[lo];
    int b = arr[mid];
    int c = arr[hi];
    if((a > b)) {
        int t = a;
        a = b;
        b = t;
    }
    if((b > c)) {
        int t = b;
        b = c;
        c = t;
    }
    if((a > b)) {
        int t = a;
        a = b;
        b = t;
    }
    return b;
}

void sort(int lo, int hi) {
    int len = (hi - lo);
    if((len <= 1)) {
        if((len == 1)) {
            markSorted(lo);
        }
        return;
    }
    if((len <= INSERTION_THRESHOLD)) {
        insertionSort(lo, hi);
        return;
    }
    int mid = (lo + (len >> 1));
    int pivot = medianOfThree(lo, mid, (hi - 1));
    recordMetric("stablePartitions");
    int* less = (int*)malloc(n * sizeof(int)); int less_len = 0;
    int* equal = (int*)malloc(n * sizeof(int)); int equal_len = 0;
    int* greater = (int*)malloc(n * sizeof(int)); int greater_len = 0;
    for(int i=lo; i<hi; i++) {
        compare(i, mid);
        int value = arr[i];
        if((value < pivot)) {
            less[less_len++] = value;
        } else if((value > pivot)) {
            greater[greater_len++] = value;
        } else {
            equal[equal_len++] = value;
        }
    }
    recordMetric("bufferedItems", len);
    int w = lo;
    for(int i=0; i<less_len; i++) {
        arr[w] = less[i];
        write(w, less[i]);
        w++;
    }
    int eqStart = w;
    for(int i=0; i<equal_len; i++) {
        arr[w] = equal[i];
        write(w, equal[i]);
        markSorted(w);
        w++;
    }
    int gtStart = w;
    for(int i=0; i<greater_len; i++) {
        arr[w] = greater[i];
        write(w, greater[i]);
        w++;
    }
    checkpoint(eqStart, n);
    sort(lo, eqStart);
    sort(gtStart, hi);
}

void sort(int arr[], int n, int* comparisons, int* swaps) {
    if((n < 2)) {
        if((n == 1)) {
            markSorted(0);
        }
        return;
    }
    int INSERTION_THRESHOLD = 24;
    int metrics = (*educational).metrics;
    metrics.insertionThreshold = INSERTION_THRESHOLD;
    sort(0, n);
    checkpoint(n, n);
} 