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) return;
  const temp = new Array(n).fill(0);
  const stackLo = new Array(n + 1).fill(0);
  const stackHi = new Array(n + 1).fill(0);
  let top = 0;
  stackLo[top] = 0;
  stackHi[top] = n - 1;
  top++;
  while (top > 0) {
    top--;
    const lo = stackLo[top];
    const hi = stackHi[top];
    if (lo >= hi) continue;
    const pivot = arr[(lo + hi) >> 1];
    let t = lo;
    for (let i = lo; i <= hi; i++) {
      if (arr[i] < pivot) {
        temp[t] = arr[i];
        t++;
      }
    }
    const ltEnd = t;
    for (let i = lo; i <= hi; i++) {
      if (arr[i] === pivot) {
        temp[t] = arr[i];
        t++;
      }
    }
    const eqEnd = t;
    for (let i = lo; i <= hi; i++) {
      if (arr[i] > pivot) {
        temp[t] = arr[i];
        t++;
      }
    }
    for (let i = lo; i <= hi; i++) {
      arr[i] = temp[i];
    }
    if (ltEnd - 1 > lo) {
      stackLo[top] = lo;
      stackHi[top] = ltEnd - 1;
      top++;
    }
    if (hi > eqEnd) {
      stackLo[top] = eqEnd;
      stackHi[top] = hi;
      top++;
    }
  }
} def sort(arr, n, stats):
    if (n < 2):
        return
    temp = [0] * n
    stackLo = [0] * (n + 1)
    stackHi = [0] * (n + 1)
    top = 0
    stackLo[top] = 0
    stackHi[top] = (n - 1)
    top += 1
    while (top > 0):
        top -= 1
        lo = stackLo[top]
        hi = stackHi[top]
        if (lo >= hi):
            continue
        pivot = arr[((lo + hi) >> 1)]
        t = lo
        for i in range(lo, (hi + 1)):
            if (arr[i] < pivot):
                temp[t] = arr[i]
                t += 1
        ltEnd = t
        for i in range(lo, (hi + 1)):
            if (arr[i] == pivot):
                temp[t] = arr[i]
                t += 1
        eqEnd = t
        for i in range(lo, (hi + 1)):
            if (arr[i] > pivot):
                temp[t] = arr[i]
                t += 1
        for i in range(lo, (hi + 1)):
            arr[i] = temp[i]
        if ((ltEnd - 1) > lo):
            stackLo[top] = lo
            stackHi[top] = (ltEnd - 1)
            top += 1
        if (hi > eqEnd):
            stackLo[top] = eqEnd
            stackHi[top] = hi
            top += 1 #include <vector>
#include <algorithm>
void sort(std::vector<int>& arr, int n, int& comparisons, int& swaps) {
    if((n < 2)) {
        return;
    }
    std::vector<int> temp(n, 0);
    std::vector<int> stackLo((n + 1), 0);
    std::vector<int> stackHi((n + 1), 0);
    int top = 0;
    stackLo[top] = 0;
    stackHi[top] = (n - 1);
    top++;
    while((top > 0)) {
        top--;
        int lo = stackLo[top];
        int hi = stackHi[top];
        if((lo >= hi)) {
            continue;
        }
        int pivot = arr[((lo + hi) >> 1)];
        int t = lo;
        for(int i=lo; i<(hi + 1); i++) {
            if((arr[i] < pivot)) {
                temp[t] = arr[i];
                t++;
            }
        }
        int ltEnd = t;
        for(int i=lo; i<(hi + 1); i++) {
            if((arr[i] == pivot)) {
                temp[t] = arr[i];
                t++;
            }
        }
        int eqEnd = t;
        for(int i=lo; i<(hi + 1); i++) {
            if((arr[i] > pivot)) {
                temp[t] = arr[i];
                t++;
            }
        }
        for(int i=lo; i<(hi + 1); i++) {
            arr[i] = temp[i];
        }
        if(((ltEnd - 1) > lo)) {
            stackLo[top] = lo;
            stackHi[top] = (ltEnd - 1);
            top++;
        }
        if((hi > eqEnd)) {
            stackLo[top] = eqEnd;
            stackHi[top] = hi;
            top++;
        }
    }
} public void Sort(int[] arr, int n, dynamic stats) {
    if((n < 2)) {
        return;
    }
    int[] temp = new int[n];
    int[] stackLo = new int[(n + 1)];
    int[] stackHi = new int[(n + 1)];
    int top = 0;
    stackLo[top] = 0;
    stackHi[top] = (n - 1);
    top++;
    while((top > 0)) {
        top--;
        int lo = stackLo[top];
        int hi = stackHi[top];
        if((lo >= hi)) {
            continue;
        }
        int pivot = arr[((lo + hi) >> 1)];
        int t = lo;
        for(int i=lo; i<(hi + 1); i++) {
            if((arr[i] < pivot)) {
                temp[t] = arr[i];
                t++;
            }
        }
        int ltEnd = t;
        for(int i=lo; i<(hi + 1); i++) {
            if((arr[i] == pivot)) {
                temp[t] = arr[i];
                t++;
            }
        }
        int eqEnd = t;
        for(int i=lo; i<(hi + 1); i++) {
            if((arr[i] > pivot)) {
                temp[t] = arr[i];
                t++;
            }
        }
        for(int i=lo; i<(hi + 1); i++) {
            arr[i] = temp[i];
        }
        if(((ltEnd - 1) > lo)) {
            stackLo[top] = lo;
            stackHi[top] = (ltEnd - 1);
            top++;
        }
        if((hi > eqEnd)) {
            stackLo[top] = eqEnd;
            stackHi[top] = hi;
            top++;
        }
    }
} #include <stdio.h>
#include <string.h>
void sort(int arr[], int n, int* comparisons, int* swaps) {
    if((n < 2)) {
        return;
    }
    int temp[n]; memset(temp, 0, sizeof(temp));
    int stackLo[(n + 1)]; memset(stackLo, 0, sizeof(stackLo));
    int stackHi[(n + 1)]; memset(stackHi, 0, sizeof(stackHi));
    int top = 0;
    stackLo[top] = 0;
    stackHi[top] = (n - 1);
    top++;
    while((top > 0)) {
        top--;
        int lo = stackLo[top];
        int hi = stackHi[top];
        if((lo >= hi)) {
            continue;
        }
        int pivot = arr[((lo + hi) >> 1)];
        int t = lo;
        for(int i=lo; i<(hi + 1); i++) {
            if((arr[i] < pivot)) {
                temp[t] = arr[i];
                t++;
            }
        }
        int ltEnd = t;
        for(int i=lo; i<(hi + 1); i++) {
            if((arr[i] == pivot)) {
                temp[t] = arr[i];
                t++;
            }
        }
        int eqEnd = t;
        for(int i=lo; i<(hi + 1); i++) {
            if((arr[i] > pivot)) {
                temp[t] = arr[i];
                t++;
            }
        }
        for(int i=lo; i<(hi + 1); i++) {
            arr[i] = temp[i];
        }
        if(((ltEnd - 1) > lo)) {
            stackLo[top] = lo;
            stackHi[top] = (ltEnd - 1);
            top++;
        }
        if((hi > eqEnd)) {
            stackLo[top] = eqEnd;
            stackHi[top] = hi;
            top++;
        }
    }
} 