Algorithms at Khan Academy part 3

we'll see two other sorting algorithms, merge sort and quicksort, whose running times are better. In particular, merge sort runs in $\Theta(n \lg n)$ time in all cases, and quicksort runs in $\mathrm{\Theta }\left(n\lg n\right)$ time in the best case and on average, though its worst-case running time is $\Theta(n^2)$.

During the Mergesort process the objects of the collection are divided into two collections. To split a collection, Mergesort will take the middle of the collection and split the collection into its left and its right part.

Divide-and-conquer algorithm:

1. Divide the problem into a number of subproblems that are smaller instances of the same problem.
2. Conquer the subproblems by solving them recursively. If they are small enough, solve the subproblems as base cases.
3. Combine the solutions to the subproblems into the solution for the original problem.

Here's how merge sort uses divide-and-conquer:

1. Divide by finding the number $q$qq of the position midway between $p$pp and $r$rr. Do this step the same way we found the midpoint in binary search: add $p$pp and $r$rr, divide by 2, and round down.
2. Conquer by recursively sorting the subarrays in each of the two subproblems created by the divide step. That is, recursively sort the subarray array[p..q] and recursively sort the subarray array[q+1..r].
3. Combine by merging the two sorted subarrays back into the single sorted subarray array[p..r].

Challenge: Implement merge sort

// Takes in an array and recursively merge sorts it
var mergeSort = function(array, p, r) {
if (p < r) {
        var q = floor((p + r)/2);
        mergeSort(array, p, q);
        mergeSort(array, q + 1, r);
        merge(array, p, q,  r);
    }
};

Challenge: implement merge

var merge = function(array, p, q, r) {
    var lowHalf = [];
    var highHalf = [];

    var k = p;
    var i;
    var j;
    for (i = 0; k <= q; i++, k++) {
        lowHalf[i] = array[k];
    }
    for (j = 0; k <= r; j++, k++) {
        highHalf[j] = array[k];
    }

    k = p;
    i = 0;
    j = 0;
   
    // Repeatedly compare the lowest untaken element in
    //  lowHalf with the lowest untaken element in highHalf
    //  and copy the lower of the two back into array
    while (i<=(q-p) && j<=(r-q-1) ) {
if (lowHalf[i] < highHalf[j]) {
array[k] = lowHalf[i];
i++;
k++;
} else {
array[k] = highHalf[j];
j++;
k++;
}

}
   
    // Once one of lowHalf and highHalf has been fully copied
    //  back into array, copy the remaining elements from the
    //  other temporary array back into the array
    while (i <= (q-p)) {
array[k] = lowHalf[i];
i++;
k++;
}

while (j <= (r-q-1)) {
array[k] = highHalf[j];
j++;
k++;
}
     
};

VS quick sort: Quicksort can sort "inline" in an existing collection, e.g. it does not have to create a copy of the collection while Mergesort requires a copy.

One other thing about merge sort is worth noting. During merging, it makes a copy of the entire array being sorted, with one half in lowHalf and the other half in highHalf. Because it copies more than a constant number of elements at some time, we say that merge sort does not work in place. By contrast, both selection sort and insertion sort do work in place, since they never make a copy of more than a constant number of array elements at any one time. Computer scientists like to consider whether an algorithm works in place, because there are some systems where space is at a premium, and thus in-place algorithms are preferred.

If the amount of memory available to us is limited, it might be in our best interest to switch to another sorting algorithm like selection sort or insertion sort, since they require less memory (both of them require only constant memory, because they don't have to copy anything). Thus, it often boils down to a trade-off between memory and speed. If you're lacking in memory, you might have to use a slower or less desirable algorithm like selection sort. But if you have plenty of memory, then maybe you can afford a faster algorithm like merge sort.