Merge sort is an O(n log n) comparison-based sorting algorithm.Its is
Repeatedly merge sub-lists to produce new sub-lists until there 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
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.
// return it.
// (using less than or equal prevents infinite recursion
// for a zero length m).
// 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