IT1230809

Merge sort

- takes advantage of the ease of merging already sorted lists into a new sorted list. It starts by comparing every two elements (i.e., 1 with 2, then 3 with 4...) and swapping them if the first should come after the second. It then merges each of the resulting lists of two into lists of four, then merges those lists of four, and so on; until at last two lists are merged into the final sorted list. Of the algorithms described here, this is the first that scales well to very large lists, because its worst-case running time is O(n log n).

Run-time Complexity Analysis:
Efficient and effective

Code:
function merge_sort(m)
var list left, right, result
if length(m) ≤ 1
return m
// This calculation is for 1-based arrays.
For 0-based, use length(m)/2 - 1.
var middle = length(m) / 2
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)
result = merge(left, right)
return result

Application: Merging a bundle of something like sticks and other.

Reference:
en.wikipedia.org/wiki/Merge_sort
http://en.wikipedia.org/wiki/Sorting_algorithm#Merge_sort