scala sort

InsertionSort.scala

object InsertionSort{	
	def sort(xs : List[Int]): List[Int] = {
	  def insert(sorted : List[Int], e : Int)= {
	  	sorted.takeWhile( x => (x < e)) ++ List(e) ++ sorted.dropWhile( x => (x < e))
	  }
	  xs.foldLeft(List[Int]()) { (sorted, e) => insert(sorted, e) }
	}           
}

MergeSort.scala

object MergeSort{
  
	def getMid(length: Int) : Int = {
		length/2
	}
	
	def merge(a : List[Int], b: List[Int]): List[Int] = {
		if(a.isEmpty) b
		else if(b.isEmpty) a
		else if(a.head < b.head) a.head +: merge(a.tail, b)
		else b.head +: merge(a, b.tail)
	}
	
	def sort(xs : List[Int]): List[Int] = {
		if(xs.length == 1) xs
		else{
			val mid = getMid(xs.length)
			merge(sort(xs.take(mid)), sort(xs.drop(mid)))
		}
	}	
	
}

MergeSortOptimized.scala

object mergeSortOptimized {
  
  	def getMid(length: Int) : Int = {
		length/2
	}
	
	def merge(a : List[Int], b: List[Int]): List[Int] = {
		if(a.isEmpty) b
		else if(b.isEmpty) a
		else if(a.last < b.head) a++b
		else if(a.head < b.head) a.head +: merge(a.tail, b)
		else b.head +: merge(a, b.tail)
	}
	
	def sort(xs : List[Int]): List[Int] = {
		if(xs.length < 7) InsertionSort.sort(xs)
		else{
			val mid = getMid(xs.length)
			merge(sort(xs.take(mid)), sort(xs.drop(mid)))
		}
	}	
 
}