Batchers Odd-Even Mergesort

function oddEvenMergeSort(arr) {
  function merge(lo, hi, step) {
    let s2 = step * 2;
    if (s2 >= hi - lo) {
      if (lo + step < hi && arr[lo] > arr[lo+step])
        [arr[lo], arr[lo+step]] = [arr[lo+step], arr[lo]];
      return;
    }
    merge(lo, hi, s2);
    merge(lo + step, hi, s2);
    for (let i = lo+step; i+step < hi; i += s2)
      if (arr[i] > arr[i+step])
        [arr[i], arr[i+step]] = [arr[i+step], arr[i]];
  }
  function sort(lo, hi) {
    if (hi - lo <= 1) return;
    let mid = (lo + hi) >> 1;
    sort(lo, mid); sort(mid, hi);
    merge(lo, hi, 1);
  }
  sort(0, arr.length);
}

def odd_even_merge_sort(arr):
    def merge(lo, hi, step):
        s2 = step * 2
        if s2 >= hi - lo:
            if lo+step < hi and arr[lo] > arr[lo+step]:
                arr[lo], arr[lo+step] = arr[lo+step], arr[lo]
            return
        merge(lo, hi, s2)
        merge(lo+step, hi, s2)
        for i in range(lo+step, hi-step, s2):
            if arr[i] > arr[i+step]:
                arr[i], arr[i+step] = arr[i+step], arr[i]
    def sort_rec(lo, hi):
        if hi - lo <= 1: return
        mid = (lo + hi) >> 1
        sort_rec(lo, mid); sort_rec(mid, hi)
        merge(lo, hi, 1)
    sort_rec(0, len(arr))

void oddEvenMergeSort(vector<int>& arr) {
  function<void(int,int,int)> merge = [&](int lo, int hi, int step) {
    int s2 = step * 2;
    if (s2 >= hi-lo) {
      if (lo+step < hi && arr[lo] > arr[lo+step])
        swap(arr[lo], arr[lo+step]);
      return;
    }
    merge(lo, hi, s2); merge(lo+step, hi, s2);
    for (int i = lo+step; i+step < hi; i += s2)
      if (arr[i] > arr[i+step]) swap(arr[i], arr[i+step]);
  };
  function<void(int,int)> sort = [&](int lo, int hi) {
    if (hi-lo <= 1) return;
    int mid = (lo+hi)>>1;
    sort(lo, mid); sort(mid, hi);
    merge(lo, hi, 1);
  };
  sort(0, arr.size());
}

void OddEvenMergeSort(int[] arr) {
  void Merge(int lo, int hi, int step) {
    int s2 = step * 2;
    if (s2 >= hi - lo) {
      if (lo+step < hi && arr[lo] > arr[lo+step])
        (arr[lo], arr[lo+step]) = (arr[lo+step], arr[lo]);
      return;
    }
    Merge(lo, hi, s2); Merge(lo+step, hi, s2);
    for (int i = lo+step; i+step < hi; i += s2)
      if (arr[i] > arr[i+step])
        (arr[i], arr[i+step]) = (arr[i+step], arr[i]);
  }
  void Sort(int lo, int hi) {
    if (hi-lo <= 1) return;
    int mid = (lo+hi) >> 1;
    Sort(lo, mid); Sort(mid, hi);
    Merge(lo, hi, 1);
  }
  Sort(0, arr.Length);
}

void oddEvenMerge(int arr[], int lo, int hi, int step) {
  int s2 = step * 2;
  if (s2 >= hi - lo) {
    if (lo+step < hi && arr[lo] > arr[lo+step]) {
      int t = arr[lo]; arr[lo] = arr[lo+step]; arr[lo+step] = t;
    }
    return;
  }
  oddEvenMerge(arr, lo, hi, s2);
  oddEvenMerge(arr, lo+step, hi, s2);
  for (int i = lo+step; i+step < hi; i += s2)
    if (arr[i] > arr[i+step]) {
      int t = arr[i]; arr[i] = arr[i+step]; arr[i+step] = t;
    }
}
void oddEvenMergeSort(int arr[], int lo, int hi) {
  if (hi - lo <= 1) return;
  int mid = (lo + hi) >> 1;
  oddEvenMergeSort(arr, lo, mid);
  oddEvenMergeSort(arr, mid, hi);
  oddEvenMerge(arr, lo, hi, 1);
}