Problem Statement

The   merge sort   is a recursive sort of order   nlog(n). It is notable for having a worst case and average complexity of   O(nlog(n)),   and a best case complexity of   O(n)   (for pre-sorted input). The basic idea is to split the collection into smaller groups by halving it until the groups only have one element or no elements   (which are both entirely sorted groups). Then merge the groups back together so that their elements are in order. This is how the algorithm gets its   divide and conquer   description.

Write a function to sort a collection of integers using the merge sort.

The merge sort algorithm comes in two parts: The functions in pseudocode look like this:

Note:   better performance can be expected if, rather than recursing until   length(m) ≤ 1,   an insertion sort is used for   length(m)   smaller than some threshold larger than   1.   However, this complicates the example code, so it is not shown here.

Let's start with the solution:

List do (
    merge := method(lst1, lst2,
        result := list()
        while(lst1 isNotEmpty or lst2 isNotEmpty,
            if(lst1 first <= lst2 first) then(
                result append(lst1 removeFirst)
            ) else (
                result append(lst2 removeFirst)
            )
        )
    result)

    mergeSort := method(
        if (size > 1) then(
            half_size := (size / 2) ceil
            return merge(slice(0, half_size) mergeSort,
                         slice(half_size, size) mergeSort)
        ) else (return self)
    )

    mergeSortInPlace := method(
        copy(mergeSort)
    )
)

lst := list(9, 5, 3, -1, 15, -2)
lst mergeSort println # ==> list(-2, -1, 3, 5, 9, 15)
lst mergeSortInPlace println # ==> list(-2, -1, 3, 5, 9, 15)