Merge Sort
This week I’m going to cover one very popular sorting algorithm – the merge sort. It’s very intuitive and simple as it’s described in Wikipedia:
- If the list is of length 0 or 1, then it is already sorted. Otherwise:
- Divide the unsorted list into two sublists of about half the size.
- Sort each sublist recursively by re-applying merge sort.
- Merge the two sublists back into one sorted list.
Here’s the Source
(JavaScript)
var a = [34, 203, 3, 746, 200, 984, 198, 764, 9];
function mergeSort(arr)
{
if (arr.length < 2)
return arr;
var middle = parseInt(arr.length / 2);
var left = arr.slice(0, middle);
var right = arr.slice(middle, arr.length);
return merge(mergeSort(left), mergeSort(right));
}
function merge(left, right)
{
var result = [];
while (left.length && right.length) {
if (left[0] <= right[0]) {
result.push(left.shift());
} else {
result.push(right.shift());
}
}
while (left.length)
result.push(left.shift());
while (right.length)
result.push(right.shift());
return result;
}
console.log(mergeSort(a)); |
var a = [34, 203, 3, 746, 200, 984, 198, 764, 9];
function mergeSort(arr)
{
if (arr.length < 2)
return arr;
var middle = parseInt(arr.length / 2);
var left = arr.slice(0, middle);
var right = arr.slice(middle, arr.length);
return merge(mergeSort(left), mergeSort(right));
}
function merge(left, right)
{
var result = [];
while (left.length && right.length) {
if (left[0] <= right[0]) {
result.push(left.shift());
} else {
result.push(right.shift());
}
}
while (left.length)
result.push(left.shift());
while (right.length)
result.push(right.shift());
return result;
}
console.log(mergeSort(a));
It’s interesting to see what happens in the Firebug’s console:
[34, 203, 3, 746] [200, 984, 198, 764, 9]
[34, 203] [3, 746]
[34] [203]
[3] [746]
[200, 984] [198, 764, 9]
[200] [984]
[198] [764, 9]
[764] [9]
[3, 9, 34, 198, 200, 203, 746, 764, 984] |
[34, 203, 3, 746] [200, 984, 198, 764, 9]
[34, 203] [3, 746]
[34] [203]
[3] [746]
[200, 984] [198, 764, 9]
[200] [984]
[198] [764, 9]
[764] [9]
[3, 9, 34, 198, 200, 203, 746, 764, 984]
Actually the tricky part in this algorithm is the merge function – it does all the work.