Ford-Johnson

function fordJohnsonSort(arr) {
  if (arr.length <= 1) return;
  // Step 1: Pair elements, swap so larger first
  const pairs = [];
  for (let i = 0; i + 1 < arr.length; i += 2)
    pairs.push(arr[i] > arr[i+1] ? [arr[i], arr[i+1]] : [arr[i+1], arr[i]]);
  // Step 2: Recursively sort by winners (first of each pair)
  const winners = pairs.map(p => p[0]);
  fordJohnsonSort(winners);
  // Step 3: Insert losers using Jacobsthal order
  const chain = [...winners];
  const losers = pairs.map(p => p[1]);
  for (const idx of jacobsthalOrder(losers.length))
    binaryInsert(chain, losers[idx]);
}

def ford_johnson_sort(arr):
    if len(arr) <= 1: return
    pairs = []
    for i in range(0, len(arr) - 1, 2):
        if arr[i] > arr[i+1]: pairs.append((arr[i], arr[i+1]))
        else: pairs.append((arr[i+1], arr[i]))
    winners = [p[0] for p in pairs]
    ford_johnson_sort(winners)
    chain = list(winners)
    losers = [p[1] for p in pairs]
    for idx in jacobsthal_order(len(losers)):
        bisect.insort(chain, losers[idx])

void fordJohnsonSort(vector<int>& arr) {
  if (arr.size() <= 1) return;
  vector<pair<int,int>> pairs;
  for (int i = 0; i + 1 < (int)arr.size(); i += 2)
    pairs.push_back(arr[i] > arr[i+1]
      ? make_pair(arr[i], arr[i+1])
      : make_pair(arr[i+1], arr[i]));
  vector<int> winners;
  for (auto& p : pairs) winners.push_back(p.first);
  fordJohnsonSort(winners);
  vector<int> chain(winners);
  for (int idx : jacobsthalOrder(pairs.size()))
    chain.insert(lower_bound(chain.begin(),
      chain.end(), pairs[idx].second),
      pairs[idx].second);
}

void FordJohnsonSort(int[] arr) {
  if (arr.Length <= 1) return;
  var pairs = new List<(int W, int L)>();
  for (int i = 0; i + 1 < arr.Length; i += 2)
    pairs.Add(arr[i] > arr[i+1]
      ? (arr[i], arr[i+1]) : (arr[i+1], arr[i]));
  var winners = pairs.Select(p => p.W).ToArray();
  FordJohnsonSort(winners);
  var chain = new List<int>(winners);
  var losers = pairs.Select(p => p.L).ToList();
  foreach (int idx in JacobsthalOrder(losers.Count))
    BinaryInsert(chain, losers[idx]);
}

void fordJohnsonSort(int arr[], int n) {
  if (n <= 1) return;
  int nPairs = n / 2;
  int win[nPairs], lose[nPairs];
  for (int i = 0; i < nPairs; i++) {
    if (arr[2*i] > arr[2*i+1])
      { win[i] = arr[2*i]; lose[i] = arr[2*i+1]; }
    else
      { win[i] = arr[2*i+1]; lose[i] = arr[2*i]; }
  }
  fordJohnsonSort(win, nPairs);
  // Insert losers via Jacobsthal order
  // using binary search into sorted chain
}