Dual-Pivot Quick Sort

function dualPivotQuickSort(arr, lo = 0, hi = arr.length-1) {
  if (lo >= hi) return;
  if (arr[lo] > arr[hi]) [arr[lo], arr[hi]] = [arr[hi], arr[lo]];
  let p = arr[lo], q = arr[hi];
  let lt = lo + 1, gt = hi - 1, k = lt;
  while (k <= gt) {
    if (arr[k] < p) { [arr[k], arr[lt]] = [arr[lt], arr[k]]; lt++; }
    else if (arr[k] > q) {
      while (arr[gt] > q && k < gt) gt--;
      [arr[k], arr[gt]] = [arr[gt], arr[k]]; gt--;
      if (arr[k] < p) { [arr[k], arr[lt]] = [arr[lt], arr[k]]; lt++; }
    }
    k++;
  }
  lt--; gt++;
  [arr[lo], arr[lt]] = [arr[lt], arr[lo]];
  [arr[hi], arr[gt]] = [arr[gt], arr[hi]];
  dualPivotQuickSort(arr, lo, lt - 1);
  dualPivotQuickSort(arr, lt + 1, gt - 1);
  dualPivotQuickSort(arr, gt + 1, hi);
}

def dual_pivot_quick_sort(arr, lo=0, hi=None):
    if hi is None: hi = len(arr) - 1
    if lo >= hi: return
    if arr[lo] > arr[hi]:
        arr[lo], arr[hi] = arr[hi], arr[lo]
    p, q = arr[lo], arr[hi]
    lt, gt, k = lo + 1, hi - 1, lo + 1
    while k <= gt:
        if arr[k] < p:
            arr[k], arr[lt] = arr[lt], arr[k]; lt += 1
        elif arr[k] > q:
            while arr[gt] > q and k < gt: gt -= 1
            arr[k], arr[gt] = arr[gt], arr[k]; gt -= 1
            if arr[k] < p:
                arr[k], arr[lt] = arr[lt], arr[k]; lt += 1
        k += 1
    lt -= 1; gt += 1
    arr[lo], arr[lt] = arr[lt], arr[lo]
    arr[hi], arr[gt] = arr[gt], arr[hi]

void dualPivotQuickSort(vector<int>& a, int lo, int hi) {
  if (lo >= hi) return;
  if (a[lo] > a[hi]) swap(a[lo], a[hi]);
  int p = a[lo], q = a[hi];
  int lt = lo+1, gt = hi-1, k = lo+1;
  while (k <= gt) {
    if (a[k] < p) swap(a[k], a[lt++]);
    else if (a[k] > q) {
      while (a[gt] > q && k < gt) gt--;
      swap(a[k], a[gt--]);
      if (a[k] < p) swap(a[k], a[lt++]);
    }
    k++;
  }
  lt--; gt++;
  swap(a[lo], a[lt]); swap(a[hi], a[gt]);
}

void DualPivotQuickSort(int[] arr, int lo, int hi) {
  if (lo >= hi) return;
  if (arr[lo] > arr[hi])
    (arr[lo], arr[hi]) = (arr[hi], arr[lo]);
  int p = arr[lo], q = arr[hi];
  int lt = lo+1, gt = hi-1, k = lo+1;
  while (k <= gt) {
    if (arr[k] < p) {
      (arr[k], arr[lt]) = (arr[lt], arr[k]); lt++;
    } else if (arr[k] > q) {
      while (arr[gt] > q && k < gt) gt--;
      (arr[k], arr[gt]) = (arr[gt], arr[k]); gt--;
      if (arr[k] < p) {
        (arr[k], arr[lt]) = (arr[lt], arr[k]); lt++;
      }
    }
    k++;
  }
}

void dualPivotQuickSort(int arr[], int lo, int hi) {
  if (lo >= hi) return;
  if (arr[lo] > arr[hi]) {
    int t = arr[lo]; arr[lo] = arr[hi]; arr[hi] = t;
  }
  int p = arr[lo], q = arr[hi];
  int lt = lo+1, gt = hi-1, k = lo+1;
  while (k <= gt) {
    if (arr[k] < p) {
      int t=arr[k]; arr[k]=arr[lt]; arr[lt]=t; lt++;
    } else if (arr[k] > q) {
      while (arr[gt] > q && k < gt) gt--;
      int t=arr[k]; arr[k]=arr[gt]; arr[gt]=t; gt--;
    }
    k++;
  }
}