mergeSort.scala

override def mergeSort[S >: T](implicit ordering: Ordering[S]): RList[S] = {

    /**
      * [3, 1, 2, 5, 4] => [[3], [1], [2], [5], [4]]
      * merge([[3], [1], [2], [5], [4]], []) // Pick two elements
      * merge ([[2], [5], [4]], [[1], [3]])
      * merge ([[4]], [[2, 5], [1, 3]]) // Now there are no two elements to pick I just prepend
      * merge ([], [[4], [2, 5], [1, 3]]) // Once getting to the empty list I call with swapped inputs
      * merge ([[4], [2, 5], [1, 3]], [])
      * merge ([[1, 3]], [[2, 4, 5]])
      * merge ([], [[1, 3], [2, 4, 5]])
      * merge ([[1, 3], [2, 4, 5]], [])
      * merge ([], [[1, 2, 3, 4, 5]])
      */
    @tailrec
    def merge(
        smallLists: RList[RList[S]],
        bigLists: RList[RList[S]]
    ): RList[S] =
      if (smallLists.isEmpty) {
        if (bigLists.isEmpty) RNil
        else if (bigLists.tail.isEmpty) bigLists.head
        else merge(bigLists, RNil)
      } else if (smallLists.tail.isEmpty) {
        if (bigLists.isEmpty) smallLists.head
        else merge(smallLists.head :: bigLists, RNil)
      } else {
        val first = smallLists.head
        val second = smallLists.tail.head
        val merged = sort(first, second, RNil)
        merge(smallLists.tail.tail, merged :: bigLists)
      }

    /**
      * sort([1, 3], [2, 4, 5, 6, 7], [])
      * sort([3], [2, 4, 5, 6, 7], [1])
      * sort([3], [4, 5, 6, 7], [1, 2])
      * sort([3], [4, 5, 6, 7], [2, 1])
      * sort([], [4, 5, 6, 7], [3, 2, 1])
      * [3, 2, 1].reverse ++ [4, 5, 6, 7]
      */
    @tailrec
    def sort(hSorted: RList[S], tSorted: RList[S], acc: RList[S]): RList[S] = {
      if (hSorted.isEmpty) acc.reverse ++ tSorted
      else if (tSorted.isEmpty) acc.reverse ++ hSorted
      else if (ordering.lteq(hSorted.head, tSorted.head))
        sort(hSorted.tail, tSorted, hSorted.head :: acc)
      else sort(hSorted, tSorted.tail, tSorted.head :: acc)
    }

    merge(this.map(_ :: RNil), RNil)
}