Fri Apr 23 2021

Merge Sort

A natural approach to problem solving is divide and conquer. In terms of sorting, a simple way to do this would be to split the list in half, sort the halves, and then merge the sorted halves together. This is the idea behind Merge sort.

Merge sort is one of the simplest sorting algorithms conceptually, and has good performance both in the asymptotic sense and in empirical running time. Surprisingly, even though it is based on a simple concept, it is relatively difficult to implement in practice.

In sorting n objects, merge sort has an average and worst-case performance of O(n log n). If the running time of merge sort for a list of length n is T(n), then the recurrence T(n) = 2T(n/2) + n.

File Name: merge-sort-algorithm.c

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

Reference:

Merge Sort

Author:Geekboots