Weak-Heap Sort

function weakHeapSort(arr) {
  const n = arr.length;
  const r = new Uint8Array(n);  // reverse bits
  // Build weak heap bottom-up
  for (let i = n - 1; i > 0; i--) {
    let j = i;
    while ((j & 1) === r[j >> 1]) j >>= 1;
    let ancestor = j >> 1;
    if (arr[ancestor] < arr[i]) {
      [arr[ancestor], arr[i]] = [arr[i], arr[ancestor]];
      r[i] ^= 1;
    }
  }
  // Extract max, sift down
  for (let i = n - 1; i > 0; i--) {
    [arr[0], arr[i]] = [arr[i], arr[0]];
    siftDown(arr, i, r, 0);
  }
}

def weak_heap_sort(arr):
    n = len(arr)
    r = [0] * n
    for i in range(n - 1, 0, -1):
        j = i
        while (j & 1) == r[j >> 1]: j >>= 1
        ancestor = j >> 1
        if arr[ancestor] < arr[i]:
            arr[ancestor], arr[i] = arr[i], arr[ancestor]
            r[i] ^= 1
    for i in range(n - 1, 0, -1):
        arr[0], arr[i] = arr[i], arr[0]
        sift_down(arr, i, r, 0)

void weakHeapSort(vector<int>& arr) {
  int n = arr.size();
  vector<int> r(n, 0);
  for (int i = n - 1; i > 0; i--) {
    int j = i;
    while ((j & 1) == r[j >> 1]) j >>= 1;
    int anc = j >> 1;
    if (arr[anc] < arr[i]) { swap(arr[anc], arr[i]); r[i] ^= 1; }
  }
  for (int i = n - 1; i > 0; i--) {
    swap(arr[0], arr[i]);
    siftDown(arr, i, r, 0);
  }
}

void WeakHeapSort(int[] arr) {
  int n = arr.Length;
  byte[] r = new byte[n];
  for (int i = n - 1; i > 0; i--) {
    int j = i;
    while ((j & 1) == r[j >> 1]) j >>= 1;
    int anc = j >> 1;
    if (arr[anc] < arr[i]) {
      (arr[anc], arr[i]) = (arr[i], arr[anc]);
      r[i] ^= 1;
    }
  }
  for (int i = n - 1; i > 0; i--) {
    (arr[0], arr[i]) = (arr[i], arr[0]);
    SiftDown(arr, i, r, 0);
  }
}

void weakHeapSort(int arr[], int n) {
  int r[n]; memset(r, 0, sizeof(r));
  for (int i = n - 1; i > 0; i--) {
    int j = i;
    while ((j & 1) == r[j >> 1]) j >>= 1;
    int anc = j >> 1;
    if (arr[anc] < arr[i]) {
      int tmp = arr[anc]; arr[anc] = arr[i]; arr[i] = tmp;
      r[i] ^= 1;
    }
  }
  for (int i = n - 1; i > 0; i--) {
    int tmp = arr[0]; arr[0] = arr[i]; arr[i] = tmp;
    siftDown(arr, i, r, 0);
  }
}