An in-place merge sort algorithm for a flattened array of pairs (i.e. Header entries)

mergesort.js

function merge(arr, start, mid, end) {
  // console.log(`m(${start}, ${mid}, ${end}) -> ${arr.slice(start, end)}`)

  for (let i = mid; i < end; i+=2) {
    let p = i
    for (let j = i - 2; j >= start; j-=2) {
      if (arr[p] < arr[j]) {
        [
          arr[p], arr[p+1],
          arr[j], arr[j+1]
        ] = [
          arr[j], arr[j+1],
          arr[p], arr[p+1]
        ]
        p = j
      }
    }
  }

  // console.log(arr)
}


function mergeSort(arr, start, end) {
  // console.log(`mS(${start}, ${end})`)
  if (start !== end - 2) {
    let div = (start + end) / 2
    let mid = div % 2 === 0 ? div : div + 1
    mergeSort(arr, start, mid)
    mergeSort(arr, mid, end)
    merge(arr, start, mid, end)
  }
}

/*
['f', 6, 'e', 5, 'd', 4, 'c', 3, 'b', 2, 'a', 1]
mS(0, 12) ['f', 6, 'e', 5, 'd', 4, 'c', 3, 'b', 2, 'a', 1]
  mS(0, 6) ['f', 6, 'e', 5, 'd', 4]
    mS(0, 4) ['f', 6, 'e', 5]
      mS(0, 2) ['f', 6]
      mS(2, 4) ['e', 5]
      m(0, 2, 4) -> ['e', 5, 'f', 6, 'd', 4, 'c', 3, 'b', 2, 'a', 1]
    mS(4, 6) ['d', 4]
    m(0, 4, 6) -> ['d', 4, 'e', 5, 'f', 6, 'c', 3, 'b', 2, 'a', 1]
  mS(6, 12) ['c', 3, 'b', 2, 'a', 1]
    mS(6, 10) ['c', 3, 'b', 2]
      mS(6, 8) ['c', 3]
      mS(8, 10) ['b', 2]
      m(6, 8, 10) -> ['d', 4, 'e', 5, 'f', 6, 'b', 2, 'c', 3, 'a', 1]
    mS(10, 12) ['a', 1]
    m(6, 10, 12) -> ['d', 4, 'e', 5, 'f', 6, 'a', 1, 'b', 2, 'c', 3]
m(0, 6, 12) -> ['a', 1, 'b', 2, 'c', 3, 'd', 4, 'e', 5, 'f', 6]
*/

const input = [
  'd', 4,
  'f', 6,
  'c', 3,
  'a', 1,
  'b', 2,
  'e', 5
]
const input2 = [
  'f', 6,
  'e', 5,
  'd', 4,
  'c', 3,
  'b', 2,
  'a', 1,
]