mergesort

gistfile1.txt

object Mergesort {

  def sort(items: List[Int], sorter: (Int, Int) => Boolean): List[Int] = {
    if (items.length == 0) {
      List[Int]();
    } else if (items.length == 1) {
      items;
    } else {
      merge(
        sort(items.slice(0, items.length / 2), sorter),
        sort(items.slice(items.length / 2, items.length), sorter),
        List[Int](),
        sorter);
    }
  }

  def merge(
    items1: List[Int],
    items2: List[Int], sorted: List[Int],
    ascending: (Int, Int) => Boolean): List[Int] = {
    (items1, items2) match {
      case (List(), List()) => sorted
      case (List(), _) =>
        merge(items1, items2.drop(1), sorted ::: List(items2.head), ascending)
      case (_, List()) =>
        merge(items1.drop(1), items2, sorted ::: List(items1.head), ascending)
      case _ => {
        if (ascending(items1.head, items2.head)) {
          merge(items1.drop(1), items2, sorted ::: (List(items1.head)), ascending);
        } else {
          merge(items1, items2.drop(1), sorted ::: (List(items2.head)), ascending);
        }
      }
    }
  }

  def main(args: Array[String]): Unit = {
	  // Example
	  val sorted = sort(List[Int](4, 2, 35, 1, 8, 79, 60), (a, b) => a <= b);
	  println(sorted.mkString(","))
  }

}