Skip to content

Instantly share code, notes, and snippets.

@chenharryhua
Last active March 21, 2021 07:02
Show Gist options
  • Save chenharryhua/22b893179d7b7d4a5e28f2a15aea0d8b to your computer and use it in GitHub Desktop.
Save chenharryhua/22b893179d7b7d4a5e28f2a15aea0d8b to your computer and use it in GitHub Desktop.
// https://www.hackerrank.com/challenges/insertion-sort/problem
def insertionSort(arr: Array[Int]): Int =
arr
.foldLeft((TreeMap.empty[Int, Int], 0L)) { case ((tm, s), (v)) =>
val d = tm.rangeFrom(v + 1).values.sum
val up = tm.updatedWith(v) {
case Some(x) => Some(x + 1)
case None => Some(1)
}
(up, s + d)
}
._2
@chenharryhua
Copy link
Author

chenharryhua commented Mar 21, 2021

  def merge(arr: Array[Int], start: Int, mid: Int, end: Int): Long = {
    val left  = arr.slice(start, mid) :+ Int.MaxValue
    val right = arr.slice(mid, end + 1) :+ Int.MaxValue
    (start to end)
      .foldLeft((0, 0, 0L)) { case ((l, r, c), i) =>
        if (left(l) <= right(r)) {
          arr(i) = left(l)
          (l + 1, r, c)
        } else {
          arr(i) = right(r)
          (l, r + 1, c + mid + r - i)
        }
      }
      ._3
  }

  def mergeSort(arr: Array[Int], start: Int, end: Int): Long =
    if (start < end) {
      val mid    = (start + end) / 2
      val left   = mergeSort(arr, start, mid)
      val right  = mergeSort(arr, mid + 1, end)
      val merged = merge(arr, start, mid + 1, end)
      left + right + merged
    } else 0L

def insertionSort(arr: Array[Int]): Long = mergeSort(arr, 0, arr.length - 1)
 

@chenharryhua
Copy link
Author

merge sort won

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment