PmergeMe · Ford-Johnson Merge-Insertion Sort Visualizer

Build the algorithm tree

Enter 2–20 integers above and press Start. The whole algorithm unfolds as a visual tree: pairing, recursive sort, main chain + pend, Jacobsthal insertion and lower_bound — top to bottom.

try: 6 5 12 10 9 1or: 9 3 7 1 8 2 6 5

Press Start to begin.

C++ code

1// PmergeMe — Ford-Johnson Merge-Insertion Sort
2void PmergeMe::sort(std::vector<int>& vec) {
3  size_t n = vec.size();
4 
5  // ── (1) pair up consecutive elements ──
6  for (size_t i = 0; i + 1 < n; i += 2)
7    pairs.push_back({vec[i], vec[i+1]});
8  if (a >= b) { winner = a; loser = b; }
9  else        { winner = b; loser = a; }
10  int straggler = (n % 2) ? vec.back() : NONE;
11 
12  /* pairs = [(winner, loser), ...] */
13  // ── (2) recursively sort the winners ──
14  sortRecursively(winners);   // Ford-Johnson on winners
15  std::sort(pairs.begin(), pairs.end(), byWinner);
16 
17  // ── (3) build main chain + pend ──
18  for (auto &p : sortedPairs) {
19    mainChain.push_back(p.winner);
20    pend.push_back(p.loser);
21  }
22  mainChain.insert(mainChain.begin(), pend[0]);
23 
24  // ── (4) Jacobsthal decides insertion order ──
25  int jacob[] = {1, 3, 5, 11, 21, 43, 85};
26  for (size_t i = end; i > prevJacob; --i) {
27    int valToInsert = pend[i - 1];
28    auto it = std::lower_bound(
29      mainChain.begin(), mainChain.end(), val);
30    // binary search: narrow [lo, hi)
31    if (val < mainChain[mid]) hi = mid;
32    else                      lo = mid + 1;
33    mainChain.insert(it, val);
34  }
35 
36  // ── (5) straggler inserted last ──
37  if (straggler) {
38    auto it = std::lower_bound(
39      mainChain.begin(), mainChain.end(), straggler);
40    mainChain.insert(it, straggler);
41  }
42 
43  return mainChain;  // sorted
44}