object Main extends App {
	 def mergeSort[T](xs:List[T])(implicit view$1:(T) => Ordered[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(x<y) x ::merge(xs1, ys)
                else y::merge(xs, ys1)
      }
      val (left, right) = xs splitAt(n)
      merge(mergeSort(left), mergeSort(right))
    }
  }
 
  val l = List(9,8,7,6,5,4,3,2,1);
  val sortedList = mergeSort(l)
  sortedList.foreach(println)
 
  val l1 = List(9.1,8.4,7.1,6.5,5.2,4.9,3.3,2.6,1.7);
  val sortedList1 = mergeSort(l)
  sortedList1.foreach(println)
 
  case class User(n:Int) extends Ordered[User] {
    def compare(that:User) = this.n - that.n
  }
 
  val u1 = User(1);val u2 = User(2);val u3 = User(3);val u4 = User(4);val u5 = User(5);val u6 = User(6);
  val sortedUsers = mergeSort(List(u2,u4,u1,u6,u5,u3))
  println("Printing sorted Useres => ")
  sortedUsers.foreach{u => println(u.n)}
}