From b9149e400c09d1f7d4bcf607d8e7b6b2c04b33d4 Mon Sep 17 00:00:00 2001
From: =?UTF-8?q?J=C3=A9r=C3=A9my=20Zurcher?= <jeremy@asynk.ch>
Date: Thu, 9 May 2013 21:40:09 +0200
Subject: Scala : generalize merge sort

---
 Scala/sandbox/10-merge-sort.scala | 23 +++++++++++++++++++++++
 1 file changed, 23 insertions(+)

diff --git a/Scala/sandbox/10-merge-sort.scala b/Scala/sandbox/10-merge-sort.scala
index 5cf0b44..04aa38d 100644
--- a/Scala/sandbox/10-merge-sort.scala
+++ b/Scala/sandbox/10-merge-sort.scala
@@ -1,5 +1,6 @@
 object MergeSort
 {
+  import math.Ordering
 
   def msort[T](xs: List[T])(lt: (T, T) => Boolean): List[T] = {
     val n = xs.length/2
@@ -18,10 +19,32 @@ object MergeSort
     }
   }
 
+  /* def msortO[T](xs: List[T])(ord: Ordering[T]): List[T] = { */
+  def msortO[T](xs: List[T])(implicit ord: Ordering[T]): List[T] = {
+    val n = xs.length/2
+    if (n==0) xs
+    else {
+      def merge(xs: List[T], ys: List[T]): List[T] = (xs, ys) match {
+        case (Nil, ys) => ys
+        case (xs, Nil) => xs
+        case (x :: xs1, y :: ys1) => {
+          if (ord.lt(x, y)) x :: merge(xs1, ys)
+          else y :: merge(xs, ys1)
+        }
+      }
+      val (fst, snd) = xs splitAt n
+      /* merge(msortO(fst)(ord), msortO(snd)(ord)) */
+      merge(msortO(fst), msortO(snd))
+    }
+  }
+
   def run = {
     println("MergeSort")
     val nums = List(2, 8, -2, 9, 2, 6, 0, 7, 1)
     val sorted = msort(nums)((x: Int, y: Int) => x < y)
     println(sorted)
+    /* val sorted2 = msortO(nums)(Ordering.Int) */
+    val sorted2 = msortO(nums)
+    println(sorted2)
   }
 }
-- 
cgit v1.1-2-g2b99