Ford-Johnson

function fordJohnsonSort(arr, stats) {
  const n = arr.length;
  function binaryInsert(chain, elIdx, maxIdx) {
    let left = 0, right = maxIdx;
    while (left < right) {
      let mid = left + Math.floor((right - left) / 2);
      compare(chain[mid], elIdx);
      if (arr[chain[mid]] < arr[elIdx]) left = mid + 1; else right = mid;
    }
    chain.splice(left, 0, elIdx);
  }
  const J = [1, 3, 5, 11, 21, 43, 85, 171, 341, 683, 1365, 2731, 5461, 10923, 21845, 43691, 87381, 174763, 349525, 699051, 1398101];
  function fj(indices) {
    let len = indices.length;
    if (len < 2) return indices;
    let pairs = [];
    let leftOver = -1;
    for (let i = 0; i < len; i += 2) {
      if (i + 1 < len) {
        compare(indices[i], indices[i + 1]);
        if (arr[indices[i]] > arr[indices[i + 1]]) pairs.push({
          win: indices[i],
          lose: indices[i + 1]
        }); else pairs.push({
          win: indices[i + 1],
          lose: indices[i]
        });
      } else {
        leftOver = indices[i];
      }
    }
    let winners = pairs.map(p => p.win);
    let sortedWinners = fj(winners);
    let mainChain = [...sortedWinners];
    let orderedPends = [];
    for (let i = 0; i < mainChain.length; i++) {
      const w = mainChain[i];
      let p = pairs.find(x => x.win === w);
      if (p) orderedPends.push(p.lose);
    }
    if (orderedPends.length > 0) mainChain.unshift(orderedPends[0]);
    let jIdx = 1;
    while (true) {
      let jk = jIdx < J.length ? J[jIdx] : J[J.length - 1];
      let jprev = jIdx - 1 >= 0 ? J[jIdx - 1] : J[J.length - 2];
      if (jprev - 1 >= orderedPends.length) break;
      let end = Math.min(jk - 1, orderedPends.length - 1);
      let start = jprev;
      for (let i = end; i >= start; i--) {
        let p = orderedPends[i];
        let pair = pairs.find(x => x.lose === p);
        let wIdx = pair ? mainChain.indexOf(pair.win) : mainChain.length;
        if (wIdx === -1) wIdx = mainChain.length;
        binaryInsert(mainChain, p, wIdx);
      }
      jIdx++;
      if (end === orderedPends.length - 1) break;
    }
    if (leftOver !== -1) binaryInsert(mainChain, leftOver, mainChain.length);
    return mainChain;
  }
  let initialIndices = [];
  for (let i = 0; i < n; i++) initialIndices.push(i);
  let finalOrder = fj(initialIndices);
  let output = new Array(n);
  for (let i = 0; i < n; i++) output[i] = arr[finalOrder[i]];
  for (let i = 0; i < n; i++) {
    arr[i] = output[i];
    write(i, output[i]);
    markSorted(i);
  }
}

from types import SimpleNamespace

def fordJohnsonSort(arr, stats):
    def binaryInsert(chain, elIdx, maxIdx):
        left = 0
        right = maxIdx
        while (left < right):
            mid = (left + ((right - left) // 2))
            compare(chain[mid], elIdx)
            if (arr[chain[mid]] < arr[elIdx]):
                left = (mid + 1)
            else:
                right = mid
        chain.insert(left, elIdx)

    def fj(indices):
        len = len(indices)
        if (len < 2):
            return indices
        pairs = []
        leftOver = -1
        for i in range(0, len, 2):
            if ((i + 1) < len):
                compare(indices[i], indices[(i + 1)])
                if (arr[indices[i]] > arr[indices[(i + 1)]]):
                    pairs.append(SimpleNamespace(win=indices[i], lose=indices[(i + 1)]))
                else:
                    pairs.append(SimpleNamespace(win=indices[(i + 1)], lose=indices[i]))
            else:
                leftOver = indices[i]
        winners = [p.win for p in pairs]
        sortedWinners = fj(winners)
        mainChain = [*sortedWinners]
        orderedPends = []
        for i in range(len(mainChain)):
            w = mainChain[i]
            p = next((x for x in pairs if (x.win == w)), None)
            if p:
                orderedPends.append(p.lose)
        if (len(orderedPends) > 0):
            mainChain.insert(0, orderedPends[0])
        jIdx = 1
        while True:
            jk = (J[jIdx] if (jIdx < len(J)) else J[(len(J) - 1)])
            jprev = (J[(jIdx - 1)] if ((jIdx - 1) >= 0) else J[(len(J) - 2)])
            if ((jprev - 1) >= len(orderedPends)):
                break
            end = ((jk - 1) if (jk - 1) <= (len(orderedPends) - 1) else (len(orderedPends) - 1))
            start = jprev
            for i in range(end, (start - 1), -1):
                p = orderedPends[i]
                pair = next((x for x in pairs if (x.lose == p)), None)
                wIdx = (mainChain.index(pair.win) if pair else len(mainChain))
                if (wIdx == -1):
                    wIdx = len(mainChain)
                binaryInsert(mainChain, p, wIdx)
            jIdx += 1
            if (end == (len(orderedPends) - 1)):
                break
        if (leftOver != -1):
            binaryInsert(mainChain, leftOver, len(mainChain))
        return mainChain

    J = [1, 3, 5, 11, 21, 43, 85, 171, 341, 683, 1365, 2731, 5461, 10923, 21845, 43691, 87381, 174763, 349525, 699051, 1398101]
    initialIndices = []
    for i in range(n):
        initialIndices.append(i)
    finalOrder = fj(initialIndices)
    output = [0] * n
    for i in range(n):
        output[i] = arr[finalOrder[i]]
    for i in range(n):
        arr[i] = output[i]
        write(i, output[i])
        markSorted(i)

#include <vector>
#include <algorithm>
void binaryInsert(int chain, int elIdx, int maxIdx);
int fj(int indices);

void binaryInsert(int chain, int elIdx, int maxIdx) {
    int left = 0;
    int right = maxIdx;
    while((left < right)) {
        int mid = (left + ((right - left) / 2));
        compare(chain[mid], elIdx);
        if((arr[chain[mid]] < arr[elIdx])) {
            left = (mid + 1);
        } else {
            right = mid;
        }
    }
    chain.insert(chain.begin() + left, elIdx);
}

int fj(int indices) {
    int len = n;
    if((len < 2)) {
        return indices;
    }
    std::vector<int> pairs;
    int leftOver = -1;
    for(int i=0; i<len; i+=2) {
        if(((i + 1) < len)) {
            compare(indices[i], indices[(i + 1)]);
            if((arr[indices[i]] > arr[indices[(i + 1)]])) {
                pairs.push_back({win: indices[i], lose: indices[(i + 1)]});
            } else {
                pairs.push_back({win: indices[(i + 1)], lose: indices[i]});
            }
        } else {
            leftOver = indices[i];
        }
    }
    std::vector<int> winners(n); for(int _mi=0;_mi<n;_mi++) { int p=pairs[_mi]; winners[_mi]=p.win; }
    int sortedWinners = fj(winners);
    std::vector<int> mainChain = {sortedWinners};
    std::vector<int> orderedPends;
    for(int i=0; i<(int)mainChain.size(); i++) {
        int w = mainChain[i];
        int p = -1; for(int _fi=0;_fi<n;_fi++) { int x=pairs[_fi]; if((x.win == w)) { p=pairs[_fi]; break; } }
        if(p) {
            orderedPends.push_back(p.lose);
        }
    }
    if(((int)orderedPends.size() > 0)) {
        mainChain.insert(mainChain.begin() + 0, orderedPends[0]);
    }
    int jIdx = 1;
    while(1) {
        int jk = (((jIdx < n)) ? (J[jIdx]) : (J[(n - 1)]));
        int jprev = ((((jIdx - 1) >= 0)) ? (J[(jIdx - 1)]) : (J[(n - 2)]));
        if(((jprev - 1) >= (int)orderedPends.size())) {
            break;
        }
        int end = (((jk - 1)) < (((int)orderedPends.size() - 1)) ? ((jk - 1)) : (((int)orderedPends.size() - 1)));
        int start = jprev;
        for(int i=end; i>(start - 1); i--) {
            int p = orderedPends[i];
            int pair = -1; for(int _fi=0;_fi<n;_fi++) { int x=pairs[_fi]; if((x.lose == p)) { pair=pairs[_fi]; break; } }
            int wIdx = ((pair) ? ((std::find(mainChain.begin(), mainChain.end(), pair.win) - mainChain.begin())) : ((int)mainChain.size()));
            if((wIdx == -1)) {
                wIdx = (int)mainChain.size();
            }
            binaryInsert(mainChain, p, wIdx);
        }
        jIdx++;
        if((end == ((int)orderedPends.size() - 1))) {
            break;
        }
    }
    if((leftOver != -1)) {
        binaryInsert(mainChain, leftOver, (int)mainChain.size());
    }
    return mainChain;
}

void sort(std::vector<int>& arr, int n, int& comparisons, int& swaps) {
    std::vector<int> J = {1, 3, 5, 11, 21, 43, 85, 171, 341, 683, 1365, 2731, 5461, 10923, 21845, 43691, 87381, 174763, 349525, 699051, 1398101};
    std::vector<int> initialIndices;
    for(int i=0; i<n; i++) {
        initialIndices.push_back(i);
    }
    int finalOrder = fj(initialIndices);
    std::vector<int> output(n, 0);
    for(int i=0; i<n; i++) {
        output[i] = arr[finalOrder[i]];
    }
    for(int i=0; i<n; i++) {
        arr[i] = output[i];
        write(i, output[i]);
        markSorted(i);
    }
}

void binaryInsert(int chain, int elIdx, int maxIdx) {
    int left = 0;
    int right = maxIdx;
    while((left < right)) {
        int mid = (left + ((right - left) / 2));
        compare(chain[mid], elIdx);
        if((arr[chain[mid]] < arr[elIdx])) {
            left = (mid + 1);
        } else {
            right = mid;
        }
    }
    chain_insert(left, elIdx);
}

int fj(int indices) {
    int len = n;
    if((len < 2)) {
        return indices;
    }
    var pairs = new List<int>();
    int leftOver = -1;
    for(int i=0; i<len; i+=2) {
        if(((i + 1) < len)) {
            compare(indices[i], indices[(i + 1)]);
            if((arr[indices[i]] > arr[indices[(i + 1)]])) {
                pairs.Add({win: indices[i], lose: indices[(i + 1)]});
            } else {
                pairs.Add({win: indices[(i + 1)], lose: indices[i]});
            }
        } else {
            leftOver = indices[i];
        }
    }
    int[] winners = new int[n]; for(int _mi=0;_mi<n;_mi++) { int p=pairs[_mi]; winners[_mi]=p.win; }
    int sortedWinners = fj(winners);
    var mainChain = new List<int> { sortedWinners };
    var orderedPends = new List<int>();
    for(int i=0; i<mainChain.Count; i++) {
        int w = mainChain[i];
        int p = -1; for(int _fi=0;_fi<n;_fi++) { int x=pairs[_fi]; if((x.win == w)) { p=pairs[_fi]; break; } }
        if(p) {
            orderedPends.Add(p.lose);
        }
    }
    if((orderedPends.Count > 0)) {
        mainChain.Insert(0, orderedPends[0]);
    }
    int jIdx = 1;
    while(true) {
        int jk = (((jIdx < n)) ? (J[jIdx]) : (J[(n - 1)]));
        int jprev = ((((jIdx - 1) >= 0)) ? (J[(jIdx - 1)]) : (J[(n - 2)]));
        if(((jprev - 1) >= orderedPends.Count)) {
            break;
        }
        int end = Math.Min((jk - 1), (orderedPends.Count - 1));
        int start = jprev;
        for(int i=end; i>(start - 1); i--) {
            int p = orderedPends[i];
            int pair = -1; for(int _fi=0;_fi<n;_fi++) { int x=pairs[_fi]; if((x.lose == p)) { pair=pairs[_fi]; break; } }
            int wIdx = ((pair) ? (Array.IndexOf(mainChain, pair.win)) : (mainChain.Count));
            if((wIdx == -1)) {
                wIdx = mainChain.Count;
            }
            binaryInsert(mainChain, p, wIdx);
        }
        jIdx++;
        if((end == (orderedPends.Count - 1))) {
            break;
        }
    }
    if((leftOver != -1)) {
        binaryInsert(mainChain, leftOver, mainChain.Count);
    }
    return mainChain;
}

public void Sort(int[] arr, int n, dynamic stats) {
    var J = new List<int> { 1, 3, 5, 11, 21, 43, 85, 171, 341, 683, 1365, 2731, 5461, 10923, 21845, 43691, 87381, 174763, 349525, 699051, 1398101 };
    var initialIndices = new List<int>();
    for(int i=0; i<n; i++) {
        initialIndices.Add(i);
    }
    int finalOrder = fj(initialIndices);
    int[] output = new int[n];
    for(int i=0; i<n; i++) {
        output[i] = arr[finalOrder[i]];
    }
    for(int i=0; i<n; i++) {
        arr[i] = output[i];
        write(i, output[i]);
        markSorted(i);
    }
}

#include <stdio.h>
#include <stdlib.h>
void binaryInsert(int chain, int elIdx, int maxIdx);
int fj(int indices);

void binaryInsert(int chain, int elIdx, int maxIdx) {
    int left = 0;
    int right = maxIdx;
    while((left < right)) {
        int mid = (left + ((right - left) / 2));
        compare(chain[mid], elIdx);
        if((arr[chain[mid]] < arr[elIdx])) {
            left = (mid + 1);
        } else {
            right = mid;
        }
    }
    chain_insert(left, elIdx);
}

int fj(int indices) {
    int len = n;
    if((len < 2)) {
        return indices;
    }
    int* pairs = (int*)malloc(n * sizeof(int)); int pairs_len = 0;
    int leftOver = -1;
    for(int i=0; i<len; i+=2) {
        if(((i + 1) < len)) {
            compare(indices[i], indices[(i + 1)]);
            if((arr[indices[i]] > arr[indices[(i + 1)]])) {
                pairs[pairs_len++] = {win: indices[i], lose: indices[(i + 1)]};
            } else {
                pairs[pairs_len++] = {win: indices[(i + 1)], lose: indices[i]};
            }
        } else {
            leftOver = indices[i];
        }
    }
    int* winners = (int*)malloc((n) * sizeof(int)); for(int _mi=0;_mi<n;_mi++) { int p=pairs[_mi]; winners[_mi]=p.win; }
    int sortedWinners = fj(winners);
    int* mainChain = (int*)malloc(n * sizeof(int)); int mainChain_len = 1;
    mainChain[0] = sortedWinners;
    int* orderedPends = (int*)malloc(n * sizeof(int)); int orderedPends_len = 0;
    for(int i=0; i<mainChain_len; i++) {
        int w = mainChain[i];
        int p = -1; for(int _fi=0;_fi<n;_fi++) { int x=pairs[_fi]; if((x.win == w)) { p=pairs[_fi]; break; } }
        if(p) {
            orderedPends[orderedPends_len++] = p.lose;
        }
    }
    if((orderedPends_len > 0)) {
        mainChain_insert(0, orderedPends[0]);
    }
    int jIdx = 1;
    while(1) {
        int jk = (((jIdx < n)) ? (J[jIdx]) : (J[(n - 1)]));
        int jprev = ((((jIdx - 1) >= 0)) ? (J[(jIdx - 1)]) : (J[(n - 2)]));
        if(((jprev - 1) >= orderedPends_len)) {
            break;
        }
        int end = (((jk - 1)) < ((orderedPends_len - 1)) ? ((jk - 1)) : ((orderedPends_len - 1)));
        int start = jprev;
        for(int i=end; i>(start - 1); i--) {
            int p = orderedPends[i];
            int pair = -1; for(int _fi=0;_fi<n;_fi++) { int x=pairs[_fi]; if((x.lose == p)) { pair=pairs[_fi]; break; } }
            int wIdx = ((pair) ? (mainChain_indexOf(pair.win)) : (mainChain_len));
            if((wIdx == -1)) {
                wIdx = mainChain_len;
            }
            binaryInsert(mainChain, p, wIdx);
        }
        jIdx++;
        if((end == (orderedPends_len - 1))) {
            break;
        }
    }
    if((leftOver != -1)) {
        binaryInsert(mainChain, leftOver, mainChain_len);
    }
    return mainChain;
}

void sort(int arr[], int n, int* comparisons, int* swaps) {
    int* J = (int*)malloc(n * sizeof(int)); int J_len = 21;
    J[0] = 1;
    J[1] = 3;
    J[2] = 5;
    J[3] = 11;
    J[4] = 21;
    J[5] = 43;
    J[6] = 85;
    J[7] = 171;
    J[8] = 341;
    J[9] = 683;
    J[10] = 1365;
    J[11] = 2731;
    J[12] = 5461;
    J[13] = 10923;
    J[14] = 21845;
    J[15] = 43691;
    J[16] = 87381;
    J[17] = 174763;
    J[18] = 349525;
    J[19] = 699051;
    J[20] = 1398101;
    int* initialIndices = (int*)malloc(n * sizeof(int)); int initialIndices_len = 0;
    for(int i=0; i<n; i++) {
        initialIndices[initialIndices_len++] = i;
    }
    int finalOrder = fj(initialIndices);
    int* output = (int*)malloc((n) * sizeof(int));
    for(int i=0; i<n; i++) {
        output[i] = arr[finalOrder[i]];
    }
    for(int i=0; i<n; i++) {
        arr[i] = output[i];
        write(i, output[i]);
        markSorted(i);
    }
}