Merge Sort Algorithm in JavaScript (with Comments)

mergeSortAlgorithm.js

/** 
* Merge Sort Algorithm: "divide and conquer", "break you down in order to build you back up"
*   Overview:
*   ---------
*   A recursive sorting algorithm where we 1) divide an unsorted array in half (dismantle big array into tiny sub-arrays)
*   until we reach atomic values (< 2 - it's never 0), then we 2) sort the adjacent sub-arrays (left, right) and 
*   3) merge the sorted sub-array values (put things back together) after each iteration
*
*   Time Complexity (worst case):
*   -----
*   n log(n) - unlike log(n base 2), at each level we don't halve our cost (remove half the problem space), we maintain
*              the cost at each level. The problem space is halved at each level, but cost stays the same.
*
*   Physical Example:
*   -----------------
*   Given 1000 people (all standing unordered) we want to take a company photo resembling a cell tower logo (small bar to big bar). 
*   Approximately halved, we divide everyone into smaller and smaller groups (500/500...250/250,250/250), until they are left standing
*   on the grass separated, but next to another person. We then organize each group based on the persons' declared heights (in cm's)
*   smallest to largest by comparing the first people in each ordered group (left and right groups) removing the smaller of the two people
*   and organizing that person into a new, growing, combined group.
*   
*   We repeat this until we're done! Eventually, we get back to 500/500 and build a new group by comparing the first people in the left 
*   and right groups, removing the smaller of the two people into our new group (which will eventually equal 1000).
*
* @param arrayToSort {arr} - unsorted array of preferably 2, or more, values
* @returns {arr} - sorted array; empty array (within recursion)
*/
function mergeSort(arrayToSort) {
    // Smallest / Base case: arrays with fewer than 2 elements are *technically* sorted
    // NOTE: the function will run a few times, before reaching this point;
    //       simply dividing in half the data, before realizing it's down to 1 item in the array
    //       and now we begin returning data to compare (merge) and we won't enter back into this code block.
    if (arrayToSort.length < 2) {
        return arrayToSort;
    }

    // 1) divide the given array's length in half - approx. (Math.floor) - to get the middle index
    var midIndex = Math.floor(arrayToSort.length / 2);
    // 1.1) use the middle index as a starting point for the knife to cut (.slice()) the array into new halves
    //      until we get all the way down to 1 item in each of the arrays
    var left  = arrayToSort.slice(0, midIndex);
    var right = arrayToSort.slice(midIndex);

    // 2) recusively call our function to break the pieces down even smaller until we reach 1 item in the array(s).
    //    NOTE: we call recursively 2 times for each iteration, left and right, in order to deconstruct each 
    //          side until it returns an array with a value(s). This adds 2 calls to the JS stack for every 1.
    //          Without recursion we could not build the array to our final, sorted array.
    var sortedLeft  = mergeSort(left);
    var sortedRight = mergeSort(right);
    // @DEBUG - see the calls return data
    // console.log('sortLeft', sortedLeft)
    // console.log('sortRight', sortedRight)

    // Create each iteration a fresh empty array to insert our sorted halves
    // NOTE: this array is also used inside our recursive calls to return either as empty,
    //       as a partially sorted section of the whole. Eventually this array is the final, sorted array at the end.
    var sortedArray = [];

    // 3) Begin to merge (broken down: an append operation after comparison operation ) 
    //    if the `sortedLeft `and `sortedRight`	recursive calls return each a [sorted] array,
    //    then we now must combine them, as a rule starting with the first value in each (index 0).
    //    Then we "pluck"/remove that value from the left or right arrays (otherwise a call stack error will surely follow)
    //    and place it in the new array (`sortedArray`) in a natural ascending, ordered position.
    //
    //    TIP: The array accumulation is not magic (just hard to visualise) as a single call produces two more calls,
    //         which return at lines 44 and 45 (viz.: left, right), and we repeat this until `sortedLeft` and `sortedRight` are empty.
    //         Remember, the left and right arrays are simply our intermediary, workhorse sub-arrays; 
    //         `sortedArray` is the simple array which accumulates the spoils.
    while (sortedLeft.length || sortedRight.length) {
        // sortedLeft's first element comes next
        // if it's less than sortedRight's first
        // element or if sortedRight is empty

        // if left has stuff in it AND there's nothing in right / first value in left is lesser than first value in right 
        // then do operation
        if (sortedLeft.length && (!sortedRight.length ||
            sortedLeft[0] < sortedRight[0])) {

            // append our value to `sortedArray` (returned and now removed in-place from the `sortedLeft` array)
            sortedArray.push(sortedLeft.shift());
        // there's nothing in the left array, or right has length and is larger than the left's value 
        } else {
            // append our value to `sortedArray` (returned and now removed in-place from the `sortedRight` array)
            sortedArray.push(sortedRight.shift());
        }
    }
    // @DEBUG - watch it grow-w-ww!
    // console.log(sortedArray)
    return sortedArray;
}

// unordered array to sort
var sortThisArray = [3545,12,4,65,2,543,546,23,89]
// initialise the sort by calling `mergeSort`
mergeSort(sortThisArray)