Merge Sort Algorithm in C

Merge sort is an O(n log n) comparison-based sorting algorithm.Its is

a type of stable sort, which means that its implementation preserves 

the input order of equal elements in the sorted output. Merge sort 

is a divide and conquer algorithm. It was invented by John von 

Neumann in 1945.

Conceptually, a merge sort works as follows:
Divide the unsorted list into 'n' sub-lists, each containing 1 element

(a list of 1 element is considered sorted).

Repeatedly merge sub-lists to produce new sub-lists until there is 

only 1 sub-list remaining. This will be the sorted list.

Algorithm for Merge Sort:

function merge_sort(list m)

// if list size is 0 (empty) or 1, consider it sorted and 
// return it.

// (using less than or equal prevents infinite recursion 
// for a zero length m).

   if length(m) <= 1

     return m

// else list size is > 1, so split the list into two sublists

    var list left, right

    var integer middle = length(m) / 2

    for each x in m before middle

         add x to left

    for each x in m after or equal middle

         add x to right

// recursively call merge_sort() to further split each sublist

// until sublist size is 1

    left = merge_sort(left)

    right = merge_sort(right)

// merge the sublists returned from prior calls to merge_sort()

// and return the resulting merged sublist

   return merge(left, right)

function merge(left, right)

    var list result

    while length(left) > 0 or length(right) > 0

        if length(left) > 0 and length(right) > 0

            if first(left) <= first(right)

                append first(left) to result

                left = rest(left)

            else

                append first(right) to result

                right = rest(right)

        else if length(left) > 0

            append first(left) to result

            left = rest(left)

        else if length(right) > 0

            append first(right) to result

            right = rest(right)

    end while

    return result