3-Way Quicksort

function quick3WaySort(arr, stats) {
  const n = arr.length;
  function sort(lo, hi) {
    if (lo >= hi) return;
    const pivot = arr[lo];
    let lt = lo;
    let i = lo + 1;
    let gt = hi;
    while (i <= gt) {
      compare(i, lo);
      if (arr[i] < pivot) {
        if (i !== lt) {
          swap(i, lt);
          const t = arr[i];
          arr[i] = arr[lt];
          arr[lt] = t;
        }
        i++;
        lt++;
      } else if (arr[i] > pivot) {
        swap(i, gt);
        const t = arr[i];
        arr[i] = arr[gt];
        arr[gt] = t;
        gt--;
      } else {
        i++;
      }
    }
    sort(lo, lt - 1);
    sort(gt + 1, hi);
  }
  sort(0, n - 1);
}

def sort(arr, n, stats):
    def sort(lo, hi):
        if (lo >= hi):
            return
        pivot = arr[lo]
        lt = lo
        i = (lo + 1)
        gt = hi
        while (i <= gt):
            if (arr[i] < pivot):
                if (i != lt):
                    t = arr[i]
                    arr[i] = arr[lt]
                    arr[lt] = t
                i += 1
                lt += 1
            elif (arr[i] > pivot):
                t = arr[i]
                arr[i] = arr[gt]
                arr[gt] = t
                gt -= 1
            else:
                i += 1
        sort(lo, (lt - 1))
        sort((gt + 1), hi)
    sort(0, (n - 1))

#include <vector>
#include <algorithm>
void sort(std::vector<int>& arr, int n, int& comparisons, int& swaps) {
    void sort(int lo, int hi) {
        if((lo >= hi)) {
            return;
        }
        int pivot = arr[lo];
        int lt = lo;
        int i = (lo + 1);
        int gt = hi;
        while((i <= gt)) {
            if((arr[i] < pivot)) {
                if((i != lt)) {
                    int t = arr[i];
                    arr[i] = arr[lt];
                    arr[lt] = t;
                }
                i++;
                lt++;
            } else if((arr[i] > pivot)) {
                int t = arr[i];
                arr[i] = arr[gt];
                arr[gt] = t;
                gt--;
            } else {
                i++;
            }
        }
        sort(lo, (lt - 1));
        sort((gt + 1), hi);
    }
    sort(0, (n - 1));
}

public void Sort(int[] arr, int n, dynamic stats) {
    void sort(int lo, int hi) {
        if((lo >= hi)) {
            return;
        }
        int pivot = arr[lo];
        int lt = lo;
        int i = (lo + 1);
        int gt = hi;
        while((i <= gt)) {
            if((arr[i] < pivot)) {
                if((i != lt)) {
                    int t = arr[i];
                    arr[i] = arr[lt];
                    arr[lt] = t;
                }
                i++;
                lt++;
            } else if((arr[i] > pivot)) {
                int t = arr[i];
                arr[i] = arr[gt];
                arr[gt] = t;
                gt--;
            } else {
                i++;
            }
        }
        sort(lo, (lt - 1));
        sort((gt + 1), hi);
    }
    sort(0, (n - 1));
}

#include <stdio.h>
void sort(int arr[], int n, int* comparisons, int* swaps) {
    void sort(int lo, int hi) {
        if((lo >= hi)) {
            return;
        }
        int pivot = arr[lo];
        int lt = lo;
        int i = (lo + 1);
        int gt = hi;
        while((i <= gt)) {
            if((arr[i] < pivot)) {
                if((i != lt)) {
                    int t = arr[i];
                    arr[i] = arr[lt];
                    arr[lt] = t;
                }
                i++;
                lt++;
            } else if((arr[i] > pivot)) {
                int t = arr[i];
                arr[i] = arr[gt];
                arr[gt] = t;
                gt--;
            } else {
                i++;
            }
        }
        sort(lo, (lt - 1));
        sort((gt + 1), hi);
    }
    sort(0, (n - 1));
}