re: Microbenchmarking your Scala Code VIEW POST

TOP OF THREAD FULL DISCUSSION
re: I agree with you that it is indeed not very efficient. It basically requires you to copy the data two times. If you want to use the already highly ...
 

I wrote a simple merge sort which is not tail recursive and compared the Scala sorted and mine on linked lists. Our intuition seems to be correct, you can be more efficient if you put some effort to adjust the algorithm.

  def merge(xs: List[Int], ys: List[Int]): List[Int] =
    (xs, ys) match {
      case (Nil, l) => l
      case (l, Nil) => l
      case (xh :: xt, yh :: yt) =>
        if (xh <= yh)
          xh :: merge(xt, ys)
        else
          yh :: merge(xs, yt)
    }

  def sort(xs: List[Int]): List[Int] =
    xs match {
      case Nil         => Nil
      case head :: Nil => head :: Nil
      case xs =>
        val (left, right) = xs.splitAt(xs.length / 2)
        merge(sort(left), sort(right))
    }
  performance of "List" in {
    measure method "sorted" in {
      using(list) in { l =>
        l.sorted
      }
    }
    measure method "merge-sort" in {
      using(list) in { l =>
        sort(l)
      }
    }
  }

graph
legend

code of conduct - report abuse