🦸‍♂️ Coding Interview Hero 🦸‍♀️

Sorting algorithms

Exercice: implement the bubble sort of a List[A] with A a generic type using tail recursion.

        import scala.annotation.tailrec

class BubbleSort[A] (implicit ev: A => Ordered[A]) {
  def sort(list: List[A]): List[A] = {
    @tailrec
    def sortRec(iteration: List[A], source: List[A], result: List[A]) : List[A]= source match {
      case h1 :: h2 :: rest => if(ev(h1) > h2) sortRec(iteration, h1 :: rest, result :+ h2) else sortRec(iteration, h2 :: rest, result :+ h1)
      case l:: Nil => sortRec(iteration, Nil, result :+ l)
      case Nil => if(iteration.isEmpty) result else sortRec(iteration.dropRight(1), result, Nil )
    }

    sortRec(list, list, Nil)
  }
}
      

Question: what is the time complexity? $$ T_n = O(n^2) $$

Exercice: implement the merge sort of a List[A] with A a generic type using tail recursion.

        import scala.annotation.tailrec

class MergeSort[A](implicit ev: A => Ordered[A]) {

  def sort(list: List[A]): List[A] = {
    val m = list.length / 2
    if (m == 0) list
    else {
      @tailrec
      def merge(ls: List[A], rs: List[A], acc: List[A] = List()): List[A] = (ls, rs) match {
        case (Nil, _) => acc ++ rs
        case (_, Nil) => acc ++ ls
        case (l :: ls1, r :: rs1) =>
          if (ev(l) < r) merge(ls1, rs, acc :+ l)
          else merge(ls, rs1, acc :+ r)
      }
      val (l, r) = list splitAt m
      merge(sort(l), sort(r))
    }
  }
}
      

Question: what is the time complexity? $$ T_n = O(n\times log(n)) $$

Then running a JMH benchmark will produce such output:

Benchmark	Mode	Threads	Samples	Score	Score Error (99,9%)	Unit
sort.SortBenchmark.BubbleSort	thrpt	1	4	329,785133	128,285418	ops/s
sort.SortBenchmark.MergeSort	thrpt	1	4	14395,874073	5231,756727	ops/s

All code is available on github.