Skip to content

Instantly share code, notes, and snippets.

@sagoez

sagoez/mergeSort.scala

Created July 20, 2021 15:00
Show Gist options

  • Select an option

    Learn more about clone URLs
  • Save sagoez/d077830e2f7909415d101abfd64058d2 to your computer and use it in GitHub Desktop.

Select an option

Learn more about clone URLs
Save sagoez/d077830e2f7909415d101abfd64058d2 to your computer and use it in GitHub Desktop.
Download ZIP

Revisions

  1. sagoez revised this gist Jul 20, 2021. No changes.
  2. sagoez created this gist Jul 20, 2021.
    52 changes: 52 additions & 0 deletions mergeSort.scala
    View file
    Original file line number Diff line number Diff line change
    @@ -0,0 +1,52 @@
    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)
    }