In computer science, merge sort (also normally spelled mergesort) is an efficient, general-purpose, comparison-based sorting algorithm. A detailed description and analysis of bottom-up mergesort looked in a report by Goldstine and von Neumann as early as 1948.

repeatedly merge sublists to produce new sorted sublists until there is only one sublist remaining. divide the unsorted list into N sublists, each containing one component (a list of one component is considered sorted).

```
/**
* This file is part of Scalacaster project, https://github.com/vkostyukov/scalacaster
* and written by Vladimir Kostyukov, http://vkostyukov.ru
*
* Merge Sort http://en.wikipedia.org/wiki/Mergesort
*
* Worst - O(n log n)
* Best - O(n log n)
* Average - O(n log n)
*
* -Notes-
*
* Using mergesort is a common way to sort a singly-linked list in a functional environment.
* This implementation fits into standard requirements about performance. The only difference
* here with default imperative implementation is a way how to split a list into two parts.
* This commonly solved by using length of the list, which costs O(n) since requires to walk
* from the start to the end of this. In this implementation, list is splitted into two equal
* parts by using 'halfify' function. This function perform very simple thing - it takes first
* two elements of the list and appends them to two separate lists, which accumulate the result.
* In other words, this function append all even nodes into first part, while odd nodes into the
* second one. This can be done in O(n).
*/
def mergesort[A <% Ordered[A]](list: List[A]): List[A] = {
def sort(p: (List[A], List[A])): List[A] = p match {
case (Nil, Nil) => Nil
case (ha :: Nil, Nil) => ha :: Nil
case (Nil, hb :: Nil) => hb :: Nil
case (as, bs) => merge(halfifyAndSort(as), halfifyAndSort(bs))
}
def halfify(as: List[A]): (List[A], List[A]) = {
def loop(bs: List[A], fs: List[A], ss: List[A]): (List[A], List[A]) = bs match {
case f :: s :: r => loop(r, f :: fs, s :: ss)
case f :: Nil => (f :: fs, ss)
case Nil => (fs, ss)
}
loop(as, Nil, Nil)
}
def merge(as: List[A], bs: List[A]): List[A] = {
def loop(cs: List[A], ds: List[A], r: List[A]): List[A] = (cs, ds) match {
case (ha :: ta, hb :: tb) =>
if (ha < hb) loop(ta, ds, ha :: r)
else loop(cs, tb, hb :: r)
case (ha :: ta, Nil) => loop(ta, Nil, ha :: r)
case (Nil, hb :: tb) => loop(Nil, tb, hb :: r)
case (Nil, Nil) => r
}
loop(as, bs, Nil).reverse
}
def halfifyAndSort(as: List[A]) = sort(halfify(as))
halfifyAndSort(list)
}
```