insertionSort.scala

// 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

  final class BIT(m: Map[Int, Int] = Map.empty) {
    private val Max: Int = 10000000

    def add(key: Int): BIT = {
      val rst = LazyList.iterate(key)(s => s + (s & (-s))).takeWhile(_ < Max).foldLeft(m) { case (s, i) =>
        s.updatedWith(i)(_.map(_ + 1).orElse(Some(1)))
      }
      new BIT(rst)
    }

    def get(key: Int): Long =
      LazyList.iterate(key)(s => s - (s & (-s))).takeWhile(_ > 0).foldLeft(0L) { case (s, i) => m.getOrElse(i, 0) + s }

    override def toString: String = m.toString
  }

  def insertionSort(arr: Array[Int]): Long =
    arr
      .foldLeft((new BIT(), 0L, 0)) { case ((tm, s, idx), (v)) =>
        val d = idx - tm.get(v)
        (tm.add(v), s + d, idx + 1)
      }
      ._2

  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)
 

merge sort won