Pattern-Defeating Quicksort

function pdqSort(arr, lo = 0, hi = arr.length - 1, depth = 0) {
  while (hi - lo + 1 > 16) {
    if (depth > 2 * Math.log2(hi - lo + 1)) {
      heapSort(arr, lo, hi); return;
    }
    let pivot = ninther(arr, lo, hi);
    let [lt, gt] = partition(arr, lo, hi, pivot);
    pdqSort(arr, lo, lt - 1, depth + 1);
    lo = gt + 1; depth++;
  }
  insertionSort(arr, lo, hi);
}

def pdq_sort(arr, lo=0, hi=None, depth=0):
    if hi is None: hi = len(arr) - 1
    while hi - lo + 1 > 16:
        if depth > 2 * math.log2(hi - lo + 1):
            heap_sort(arr, lo, hi); return
        pivot = ninther(arr, lo, hi)
        lt, gt = partition(arr, lo, hi, pivot)
        pdq_sort(arr, lo, lt - 1, depth + 1)
        lo = gt + 1; depth += 1
    insertion_sort(arr, lo, hi)

void pdqSort(vector<int>& arr, int lo, int hi, int depth) {
  while (hi - lo + 1 > 16) {
    if (depth > 2 * log2(hi - lo + 1)) {
      heapSort(arr, lo, hi); return;
    }
    int pivot = ninther(arr, lo, hi);
    auto [lt, gt] = partition(arr, lo, hi, pivot);
    pdqSort(arr, lo, lt - 1, depth + 1);
    lo = gt + 1; depth++;
  }
  insertionSort(arr, lo, hi);
}

void PdqSort(int[] arr, int lo, int hi, int depth) {
  while (hi - lo + 1 > 16) {
    if (depth > 2 * Math.Log2(hi - lo + 1)) {
      HeapSort(arr, lo, hi); return;
    }
    int pivot = Ninther(arr, lo, hi);
    var (lt, gt) = Partition(arr, lo, hi, pivot);
    PdqSort(arr, lo, lt - 1, depth + 1);
    lo = gt + 1; depth++;
  }
  InsertionSort(arr, lo, hi);
}

void pdqSort(int arr[], int lo, int hi, int depth) {
  while (hi - lo + 1 > 16) {
    if (depth > 2 * log2(hi - lo + 1)) {
      heapSort(arr, lo, hi); return;
    }
    int pivot = ninther(arr, lo, hi);
    int lt, gt;
    partition(arr, lo, hi, pivot, &lt, &gt);
    pdqSort(arr, lo, lt - 1, depth + 1);
    lo = gt + 1; depth++;
  }
  insertionSort(arr, lo, hi);
}