Pattern-Defeating Quicksort

function pdqSort(arr, stats) {
  const n = arr.length;
  function ins(lo, hi) {
    for (let i = lo + 1; i <= hi; i++) {
      const key = arr[i];
      let j = i - 1;
      while (j >= lo) {
        compare(j, j + 1);
        if (arr[j] <= key) break;
        arr[j + 1] = arr[j];
        write(j + 1, arr[j + 1]);
        j--;
      }
      arr[j + 1] = key;
      write(j + 1, key);
    }
  }
  function hs(lo, hi) {
    const sz = hi - lo + 1;
    function sd(root, end) {
      let p = root;
      while (2 * (p - lo) + 1 + lo <= end) {
        let c = 2 * (p - lo) + 1 + lo;
        if (c + 1 <= end) {
          if (arr[c] < arr[c + 1]) c++;
        }
        if (arr[p] < arr[c]) {
          [arr[p], arr[c]] = [arr[c], arr[p]];
          swap(p, c);
          p = c;
        } else break;
      }
    }
    for (let i = lo + Math.floor(sz / 2) - 1; i >= lo; i--) sd(i, hi);
    for (let i = hi; i > lo; i--) {
      [arr[lo], arr[i]] = [arr[i], arr[lo]];
      sd(lo, i - 1);
    }
  }
  function swap(a, b) {
    let t = arr[a];
    arr[a] = arr[b];
    arr[b] = t;
    swap(a, b);
  }
  function pdqRec(lo, hi, limit, badLimit) {
    let len = hi - lo + 1;
    if (len < 24) {
      ins(lo, hi);
      return;
    }
    if (limit === 0) {
      hs(lo, hi);
      return;
    }
    let s = Math.floor(len / 8);
    let m = lo + Math.floor(len / 2);
    if (len > 128) {
      let l = lo;
      let r = hi;
      function sort3(a, b, c) {
        if (arr[b] < arr[a]) swap(a, b);
        if (arr[c] < arr[b]) swap(b, c);
        if (arr[b] < arr[a]) swap(a, b);
      }
      sort3(l, l + s, l + 2 * s);
      sort3(m - s, m, m + s);
      sort3(r - 2 * s, r - s, r);
      sort3(l + s, m, r - s);
    } else {
      if (arr[m] < arr[lo]) swap(lo, m);
      if (arr[hi] < arr[m]) swap(m, hi);
      if (arr[m] < arr[lo]) swap(lo, m);
    }
    if (arr[lo] > arr[hi]) swap(lo, hi);
    swap(lo, m);
    let pivot = arr[lo];
    let i = lo + 1;
    let j = hi;
    while (true) {
      while (i <= j) {
        if (arr[i] >= pivot) break;
        i++;
      }
      while (i <= j) {
        if (arr[j] <= pivot) break;
        j--;
      }
      if (i >= j) break;
      swap(i, j);
      i++;
      j--;
    }
    swap(lo, j);
    let lLen = j - lo;
    let rLen = hi - i + 1;
    let pLimit = limit;
    if (lLen < len / 8 || rLen < len / 8) {
      badLimit--;
      if (badLimit === 0) {
        pLimit = 0;
      }
    }
    if (j > lo) pdqRec(lo, j - 1, pLimit, badLimit);
    if (i < hi) pdqRec(i, hi, pLimit, badLimit);
  }
  pdqRec(0, n - 1, Math.floor(Math.log2(n)), Math.floor(Math.log2(n)));
}

def pdqSort(arr, stats):
    def ins(lo, hi):
        for i in range((lo + 1), (hi + 1)):
            key = arr[i]
            j = (i - 1)
            while (j >= lo):
                compare(j, (j + 1))
                if (arr[j] <= key):
                    break
                arr[(j + 1)] = arr[j]
                write((j + 1), arr[(j + 1)])
                j -= 1
            arr[(j + 1)] = key
            write((j + 1), key)

    def hs(lo, hi):
        sz = ((hi - lo) + 1)
        def sd(root, end):
            p = root
            while ((((2 * (p - lo)) + 1) + lo) <= end):
                c = (((2 * (p - lo)) + 1) + lo)
                if ((c + 1) <= end):
                    if (arr[c] < arr[(c + 1)]):
                        c += 1
                if (arr[p] < arr[c]):
                    arr[p], arr[c] = arr[c], arr[p]
                    swap(p, c)
                    p = c
                else:
                    break

        for i in range(((lo + (sz // 2)) - 1), (lo - 1), -1):
            sd(i, hi)
        for i in range(hi, lo, -1):
            arr[lo], arr[i] = arr[i], arr[lo]
            sd(lo, (i - 1))

    def swap(a, b):
        t = arr[a]
        arr[a] = arr[b]
        arr[b] = t
        swap(a, b)

    def pdqRec(lo, hi, limit, badLimit):
        len = ((hi - lo) + 1)
        if (len < 24):
            ins(lo, hi)
            return
        if (limit == 0):
            hs(lo, hi)
            return
        s = (len // 8)
        m = (lo + (len // 2))
        if (len > 128):
            l = lo
            r = hi
            def sort3(a, b, c):
                if (arr[b] < arr[a]):
                    swap(a, b)
                if (arr[c] < arr[b]):
                    swap(b, c)
                if (arr[b] < arr[a]):
                    swap(a, b)

            sort3(l, (l + s), (l + (2 * s)))
            sort3((m - s), m, (m + s))
            sort3((r - (2 * s)), (r - s), r)
            sort3((l + s), m, (r - s))
        else:
            if (arr[m] < arr[lo]):
                swap(lo, m)
            if (arr[hi] < arr[m]):
                swap(m, hi)
            if (arr[m] < arr[lo]):
                swap(lo, m)
        if (arr[lo] > arr[hi]):
            swap(lo, hi)
        swap(lo, m)
        pivot = arr[lo]
        i = (lo + 1)
        j = hi
        while True:
            while (i <= j):
                if (arr[i] >= pivot):
                    break
                i += 1
            while (i <= j):
                if (arr[j] <= pivot):
                    break
                j -= 1
            if (i >= j):
                break
            swap(i, j)
            i += 1
            j -= 1
        swap(lo, j)
        lLen = (j - lo)
        rLen = ((hi - i) + 1)
        pLimit = limit
        if ((lLen < (len // 8)) or (rLen < (len // 8))):
            badLimit -= 1
            if (badLimit == 0):
                pLimit = 0
        if (j > lo):
            pdqRec(lo, (j - 1), pLimit, badLimit)
        if (i < hi):
            pdqRec(i, hi, pLimit, badLimit)

    pdqRec(0, (n - 1), int((__import__("math").log2(n) if (n) > 0 else 0)), int((__import__("math").log2(n) if (n) > 0 else 0)))

#include <vector>
#include <algorithm>
#include <cmath>
void ins(int lo, int hi);
void hs(int lo, int hi);
void swap(int a, int b);
void pdqRec(int lo, int hi, int limit, int badLimit);

void ins(int lo, int hi) {
    for(int i=(lo + 1); i<(hi + 1); i++) {
        int key = arr[i];
        int j = (i - 1);
        while((j >= lo)) {
            compare(j, (j + 1));
            if((arr[j] <= key)) {
                break;
            }
            arr[(j + 1)] = arr[j];
            write((j + 1), arr[(j + 1)]);
            j--;
        }
        arr[(j + 1)] = key;
        write((j + 1), key);
    }
}

void hs(int lo, int hi) {
    int sz = ((hi - lo) + 1);
    void sd(int root, int end) {
        int p = root;
        while(((((2 * (p - lo)) + 1) + lo) <= end)) {
            int c = (((2 * (p - lo)) + 1) + lo);
            if(((c + 1) <= end)) {
                if((arr[c] < arr[(c + 1)])) {
                    c++;
                }
            }
            if((arr[p] < arr[c])) {
                std::swap(arr[p], arr[c]);
                swap(p, c);
                p = c;
            } else {
                break;
            }
        }
    }
    for(int i=((lo + (sz / 2)) - 1); i>(lo - 1); i--) {
        sd(i, hi);
    }
    for(int i=hi; i>lo; i--) {
        std::swap(arr[lo], arr[i]);
        sd(lo, (i - 1));
    }
}

void swap(int a, int b) {
    int t = arr[a];
    arr[a] = arr[b];
    arr[b] = t;
    swap(a, b);
}

void pdqRec(int lo, int hi, int limit, int badLimit) {
    int len = ((hi - lo) + 1);
    if((len < 24)) {
        ins(lo, hi);
        return;
    }
    if((limit == 0)) {
        hs(lo, hi);
        return;
    }
    int s = (len / 8);
    int m = (lo + (len / 2));
    if((len > 128)) {
        int l = lo;
        int r = hi;
        void sort3(int a, int b, int c) {
            if((arr[b] < arr[a])) {
                swap(a, b);
            }
            if((arr[c] < arr[b])) {
                swap(b, c);
            }
            if((arr[b] < arr[a])) {
                swap(a, b);
            }
        }
        sort3(l, (l + s), (l + (2 * s)));
        sort3((m - s), m, (m + s));
        sort3((r - (2 * s)), (r - s), r);
        sort3((l + s), m, (r - s));
    } else {
        if((arr[m] < arr[lo])) {
            swap(lo, m);
        }
        if((arr[hi] < arr[m])) {
            swap(m, hi);
        }
        if((arr[m] < arr[lo])) {
            swap(lo, m);
        }
    }
    if((arr[lo] > arr[hi])) {
        swap(lo, hi);
    }
    swap(lo, m);
    int pivot = arr[lo];
    int i = (lo + 1);
    int j = hi;
    while(1) {
        while((i <= j)) {
            if((arr[i] >= pivot)) {
                break;
            }
            i++;
        }
        while((i <= j)) {
            if((arr[j] <= pivot)) {
                break;
            }
            j--;
        }
        if((i >= j)) {
            break;
        }
        swap(i, j);
        i++;
        j--;
    }
    swap(lo, j);
    int lLen = (j - lo);
    int rLen = ((hi - i) + 1);
    int pLimit = limit;
    if(((lLen < (len / 8)) || (rLen < (len / 8)))) {
        badLimit--;
        if((badLimit == 0)) {
            pLimit = 0;
        }
    }
    if((j > lo)) {
        pdqRec(lo, (j - 1), pLimit, badLimit);
    }
    if((i < hi)) {
        pdqRec(i, hi, pLimit, badLimit);
    }
}

void sort(std::vector<int>& arr, int n, int& comparisons, int& swaps) {
    pdqRec(0, (n - 1), (int)std::floor((int)std::log2(n)), (int)std::floor((int)std::log2(n)));
}

void ins(int lo, int hi) {
    for(int i=(lo + 1); i<(hi + 1); i++) {
        int key = arr[i];
        int j = (i - 1);
        while((j >= lo)) {
            compare(j, (j + 1));
            if((arr[j] <= key)) {
                break;
            }
            arr[(j + 1)] = arr[j];
            write((j + 1), arr[(j + 1)]);
            j--;
        }
        arr[(j + 1)] = key;
        write((j + 1), key);
    }
}

void hs(int lo, int hi) {
    int sz = ((hi - lo) + 1);
    void sd(int root, int end) {
        int p = root;
        while(((((2 * (p - lo)) + 1) + lo) <= end)) {
            int c = (((2 * (p - lo)) + 1) + lo);
            if(((c + 1) <= end)) {
                if((arr[c] < arr[(c + 1)])) {
                    c++;
                }
            }
            if((arr[p] < arr[c])) {
                { int _t = arr[p]; arr[p] = arr[c]; arr[c] = _t; }
                swap(p, c);
                p = c;
            } else {
                break;
            }
        }
    }
    for(int i=((lo + (sz / 2)) - 1); i>(lo - 1); i--) {
        sd(i, hi);
    }
    for(int i=hi; i>lo; i--) {
        { int _t = arr[lo]; arr[lo] = arr[i]; arr[i] = _t; }
        sd(lo, (i - 1));
    }
}

void swap(int a, int b) {
    int t = arr[a];
    arr[a] = arr[b];
    arr[b] = t;
    swap(a, b);
}

void pdqRec(int lo, int hi, int limit, int badLimit) {
    int len = ((hi - lo) + 1);
    if((len < 24)) {
        ins(lo, hi);
        return;
    }
    if((limit == 0)) {
        hs(lo, hi);
        return;
    }
    int s = (len / 8);
    int m = (lo + (len / 2));
    if((len > 128)) {
        int l = lo;
        int r = hi;
        void sort3(int a, int b, int c) {
            if((arr[b] < arr[a])) {
                swap(a, b);
            }
            if((arr[c] < arr[b])) {
                swap(b, c);
            }
            if((arr[b] < arr[a])) {
                swap(a, b);
            }
        }
        sort3(l, (l + s), (l + (2 * s)));
        sort3((m - s), m, (m + s));
        sort3((r - (2 * s)), (r - s), r);
        sort3((l + s), m, (r - s));
    } else {
        if((arr[m] < arr[lo])) {
            swap(lo, m);
        }
        if((arr[hi] < arr[m])) {
            swap(m, hi);
        }
        if((arr[m] < arr[lo])) {
            swap(lo, m);
        }
    }
    if((arr[lo] > arr[hi])) {
        swap(lo, hi);
    }
    swap(lo, m);
    int pivot = arr[lo];
    int i = (lo + 1);
    int j = hi;
    while(true) {
        while((i <= j)) {
            if((arr[i] >= pivot)) {
                break;
            }
            i++;
        }
        while((i <= j)) {
            if((arr[j] <= pivot)) {
                break;
            }
            j--;
        }
        if((i >= j)) {
            break;
        }
        swap(i, j);
        i++;
        j--;
    }
    swap(lo, j);
    int lLen = (j - lo);
    int rLen = ((hi - i) + 1);
    int pLimit = limit;
    if(((lLen < (len / 8)) || (rLen < (len / 8)))) {
        badLimit--;
        if((badLimit == 0)) {
            pLimit = 0;
        }
    }
    if((j > lo)) {
        pdqRec(lo, (j - 1), pLimit, badLimit);
    }
    if((i < hi)) {
        pdqRec(i, hi, pLimit, badLimit);
    }
}

public void Sort(int[] arr, int n, dynamic stats) {
    pdqRec(0, (n - 1), (int)Math.Floor((double)(int)Math.Log((double)n, 2)), (int)Math.Floor((double)(int)Math.Log((double)n, 2)));
}

#include <stdio.h>
#include <math.h>
void ins(int lo, int hi);
void hs(int lo, int hi);
void swap(int a, int b);
void pdqRec(int lo, int hi, int limit, int badLimit);

void ins(int lo, int hi) {
    for(int i=(lo + 1); i<(hi + 1); i++) {
        int key = arr[i];
        int j = (i - 1);
        while((j >= lo)) {
            compare(j, (j + 1));
            if((arr[j] <= key)) {
                break;
            }
            arr[(j + 1)] = arr[j];
            write((j + 1), arr[(j + 1)]);
            j--;
        }
        arr[(j + 1)] = key;
        write((j + 1), key);
    }
}

void hs(int lo, int hi) {
    int sz = ((hi - lo) + 1);
    void sd(int root, int end) {
        int p = root;
        while(((((2 * (p - lo)) + 1) + lo) <= end)) {
            int c = (((2 * (p - lo)) + 1) + lo);
            if(((c + 1) <= end)) {
                if((arr[c] < arr[(c + 1)])) {
                    c++;
                }
            }
            if((arr[p] < arr[c])) {
                { int _t = arr[p]; arr[p] = arr[c]; arr[c] = _t; }
                swap(p, c);
                p = c;
            } else {
                break;
            }
        }
    }
    for(int i=((lo + (sz / 2)) - 1); i>(lo - 1); i--) {
        sd(i, hi);
    }
    for(int i=hi; i>lo; i--) {
        { int _t = arr[lo]; arr[lo] = arr[i]; arr[i] = _t; }
        sd(lo, (i - 1));
    }
}

void swap(int a, int b) {
    int t = arr[a];
    arr[a] = arr[b];
    arr[b] = t;
    swap(a, b);
}

void pdqRec(int lo, int hi, int limit, int badLimit) {
    int len = ((hi - lo) + 1);
    if((len < 24)) {
        ins(lo, hi);
        return;
    }
    if((limit == 0)) {
        hs(lo, hi);
        return;
    }
    int s = (len / 8);
    int m = (lo + (len / 2));
    if((len > 128)) {
        int l = lo;
        int r = hi;
        void sort3(int a, int b, int c) {
            if((arr[b] < arr[a])) {
                swap(a, b);
            }
            if((arr[c] < arr[b])) {
                swap(b, c);
            }
            if((arr[b] < arr[a])) {
                swap(a, b);
            }
        }
        sort3(l, (l + s), (l + (2 * s)));
        sort3((m - s), m, (m + s));
        sort3((r - (2 * s)), (r - s), r);
        sort3((l + s), m, (r - s));
    } else {
        if((arr[m] < arr[lo])) {
            swap(lo, m);
        }
        if((arr[hi] < arr[m])) {
            swap(m, hi);
        }
        if((arr[m] < arr[lo])) {
            swap(lo, m);
        }
    }
    if((arr[lo] > arr[hi])) {
        swap(lo, hi);
    }
    swap(lo, m);
    int pivot = arr[lo];
    int i = (lo + 1);
    int j = hi;
    while(1) {
        while((i <= j)) {
            if((arr[i] >= pivot)) {
                break;
            }
            i++;
        }
        while((i <= j)) {
            if((arr[j] <= pivot)) {
                break;
            }
            j--;
        }
        if((i >= j)) {
            break;
        }
        swap(i, j);
        i++;
        j--;
    }
    swap(lo, j);
    int lLen = (j - lo);
    int rLen = ((hi - i) + 1);
    int pLimit = limit;
    if(((lLen < (len / 8)) || (rLen < (len / 8)))) {
        badLimit--;
        if((badLimit == 0)) {
            pLimit = 0;
        }
    }
    if((j > lo)) {
        pdqRec(lo, (j - 1), pLimit, badLimit);
    }
    if((i < hi)) {
        pdqRec(i, hi, pLimit, badLimit);
    }
}

void sort(int arr[], int n, int* comparisons, int* swaps) {
    pdqRec(0, (n - 1), (int)floor((int)log2(n)), (int)floor((int)log2(n)));
}