Merge sort

Merge sort

Aim : To sort the given elements using Merge Sort

Algorithm:

function merge_sort(m)
var list left, right, result
if length(m) < = 1
return m
var middle = length(m) / 2 - 1
for each x in m up to middle
add x to left
for each x in m after middle
add x to right

left = merge_sort(left)
right = merge_sort(right)
if left.last_item > right.first_item
result = merge(left, right)
else
result = append(left, right)
return result

function merge(left,right)
var list result
while 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)
end while
if length(left) > 0
append left to result
else
append right to result
return result