Merge Sort Function

Take a random list and merge sorts it.

by Hugh Chapman

HTML

<div></div>

CSS

div {
    word-wrap: break-word;
}

JavaScript

var uSet = [35, 2, 51, 52, 99, 30, 91, 47, 29, 54, 11, 15, 56, 100, 79, 60, 90, 16, 24, 48, 66, 94, 68, 45, 34, 27, 77, 46, 38, 39, 83, 74, 23, 19, 85, 12, 9, 53, 67, 20, 25, 87, 98, 44, 82, 81, 1, 80, 61, 93, 65, 43, 92, 89, 36, 84, 28, 75, 97, 3, 86, 7, 31, 57, 69, 10, 22, 62, 41, 42, 32, 33, 37, 5, 71, 58, 49, 73, 17, 88, 70, 13, 40, 21, 95, 78, 4, 59, 96, 14, 50, 72, 18, 64, 26, 76, 6, 63, 55, 8];

function merge_sort(m) {
    // Base case. A list of zero or one elements is sorted, by definition.
    if (m.length <= 1) return m;

    // Recursive case. First, *divide* the list into equal-sized sublists.
    var left = [],
        right = [];
    var middle = Math.ceil(m.length / 2);
    left = m.splice(0, middle);
    right = m;

    // Recursively sort both sublists.
    left = merge_sort(left);  
    right = merge_sort(right);
    // *Conquer*: merge the now-sorted sublists.
    return merge(left, right)
}

function merge(left, right) {
    // receive the left and right sublist as arguments.
    // 'result' variable for the merged result of two sublists.
    var result = [];
    // assign the element of the sublists to 'result' variable until there is no element to merge. 
    while (left.length > 0 || right.length > 0) {
        if (left.length > 0 && right.length > 0) {
            // compare the first two element, which is the small one, of each two sublists.
            if (left[0] <= right[0]) {
                // the small element is copied to 'result' variable.
                // delete the copied one(a first element) in the sublist.
                result.push(left.shift());
            } else {
                // same operation as the above(in the right sublist).
                result.push(right.shift());
            }
        } else if (left.length > 0) {
            // copy all of remaining elements from the sublist to 'result' variable, 
            // when there is no more element to compare with.
            result.push(left.shift());
       ...