JSFiddle - React, Tailwind, and code Playground

mergeSort

by nickadeemus2002

JavaScript

/**
* ==============
* Merge sort
* ==============
*
* "Divide and conquer" algorithm.
* MergeSort is a recursive algorithm.
*
* In merge sort we divide the array
* into two equal portions, and sort
* them recursively.
*
*/


/**
* Sorts an array using merge sort
*
*   array is changed in place,
*   values are mutated.
*
*/
function mergeSort(array) {

console.log('***** mergeSort => array', array);

    var middle, left, right;

    /* case: base */
    if (array.length <= 1) {
        return array;
    }

    //  divide the array into left/right portions
    //  and sort them recursively.
    middle = Math.floor(array.length / 2);  // array middle idx
    left = array.slice(0, middle);
    right = array.slice(middle);

    // case: recurse  -
    return merge(mergeSort(left), mergeSort(right));
}

/**
*   merge:
*   One by one select the smallest
*   item, from either the left or
*   the right segment and put
*   that into the result giving us
*   the merged sorted array.
*/
function merge(leftSegment, rightSegment) {
    // final sorted array
    var mergedArray = [];
    var lIndex = 0;
    var rIndex = 0;
    // current left and right
    // item lookups.
    // when a lookup value is
    // inserted into the mergedArray
    // increment parent [lr]Index
    var lItem, rItem;

    console.log('^ merge => leftSegment', leftSegment);
    console.log('^ merge => rightSegment', rightSegment);


    // abort once we are out of
    // elements in both sub-arrays,
    // defined by total item lookups < total segements
    while ( (lIndex + rIndex)  <  (leftSegment.length + rightSegment.length) ) {

        lItem = leftSegment[lIndex];
        rItem = rightSegment[rIndex];

    console.log('^ merge => lItem', lItem);
    console.log('^ merge => rItem', rItem);

        // empty left array items.
        // use right side values
        if (lItem == null) {
            mergedArray.push(rItem);
            rIndex++;
        }
        // empty right array items.
      ...