Probably not the best way to implement it ... but I don't care at the moment, just feel happy that I did it :-)
<html> <script>
function merge(left, right){
var result = new Array();
while (left.length > 0 || right.length > 0){
var smallestElement;
if (left.length > 0 && right.length > 0){
smallestElement = left[0];
if (left[0] > right[0]){
smallestElement = right[0];
right.splice(0,1);
} else {
left.splice(0, 1);
}
} else if (left.length > 0){
smallestElement = left[0];
left.splice(0, 1);
} else {
smallestElement = right[0];
right.splice(0,1);
}
result.push(smallestElement);
}
return result;
}
function mergeSort(input){
var length = input.length;
var left = input.splice(0, length/2);
var right = input;
var leftResult;
var rightResult;
if (left.length > 1){
leftResult = mergeSort(left);
} else {
leftResult = left;
}
if (right.length > 1){
rightResult = mergeSort(right);
} else {
rightResult = right;
}
return merge(leftResult,rightResult);
}
(function(){
var testInput = new Array(6,5,3,4,2,1,8,8,9,9,10,15);
console.log(mergeSort(testInput));
}());
</script>
</html>
Very nice, not many people can actually sit down and write this without looking it up.
ReplyDelete