Merge Sort

We need to recursively do the following:

• Split array in 2.
• Have a struct with 3 values. The original array, the left side of the array and right side of the array.
• Repeat until the array is size of 1.

Then,

• Loop through the top structure, accessing the right side until size is just 1?

Here is the code in full. The first part 1 is the split, while the second part 2 is the merge. Also notice the edge cases. If p1 or p2 has reached the end, we use the other one and increment it.

func (arr *Array[T]) MergeSort() {
  var node Node[Array[T]]
  node.value = *arr

  var merge func(node *Node[Array[T]])
  merge = func(node *Node[Array[T]]) {
    l := node.left.value
    r := node.right.value

    pl, pr := 0, 0

    for i := 0; i < len(node.value); i++ {
      if pl == len(l) {
        node.value[i] = r[pr]
        pr++
        continue
      } else if pr == len(r) {
        node.value[i] = l[pl]
        pl++
        continue
      }
      if Less(l[pl], r[pr]) {
        node.value[i] = l[pl]
        pl++
      } else {
        node.value[i] = r[pr]
        pr++
      }
    }
  }

  var recursiveSplit func(node *Node[Array[T]])
  recursiveSplit = func(node *Node[Array[T]]) {
    l := len(node.value)
    m := l / 2
    if l > 1 {
      var lSide Node[Array[T]]
      var rSide Node[Array[T]]
      lSide.value = make(Array[T], len(node.value[:m]))
      rSide.value = make(Array[T], len(node.value[m:]))

      copy(lSide.value, node.value[:m])
      copy(rSide.value, node.value[m:])

      node.left = &lSide
      node.right = &rSide

      recursiveSplit(&lSide)
      recursiveSplit(&rSide)

      merge(node)
    }
  }

  recursiveSplit(&node)
}

To figure this out, we need to understand a few things:

• We cannot merge until the sub arrays are sorted.
• While merging, the current node’s value is not important (we may overwrite it)
• merge(node) (3) will not run until the children have been merged, so we can trust it is sorted.

A stumbling block I had was to split everything, and then merge everything. This was a mistake. Instead, we merge right after we call recursiveSplit and the left and right side 3 . This allows us to keep track of where we are. Originally, I had code trying to identify how to keep state, which I later realized I was throwing away by completing the full split before attempting the merge.

A realization I had is during recursion, you should always trust that whatever recursive function you called will be done by the time the next statement runs. It’s tricky to mentally wrap my mind around recursion, and this helped clarify it for me.

• Bro Code - Learn Merge Sort in 13 minutes