Skip to content

Instantly share code, notes, and snippets.

@samgj18
Created July 20, 2021 15:00
Show Gist options
  • Save samgj18/d077830e2f7909415d101abfd64058d2 to your computer and use it in GitHub Desktop.
Save samgj18/d077830e2f7909415d101abfd64058d2 to your computer and use it in GitHub Desktop.
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)
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment