Merge sort in JavaScript

Merge sort follows the divide and conquer approach to sort the given list. The important step in this sorting approach is the merging step.


function merge(lo, m, hi) {
    var i, j, k;
    i=0; j=lo;
    // copy first half of array a to auxiliary array b
    while (j<=m)
        b[i++] = a[j++];

    i=0; k=lo;
    // copy back next-greatest element at each time
    while (k<j && j<=hi)
        if (b[i]<=a[j])
            a[k++]=b[i++];
        else
            a[k++]=a[j++];

    // copy back remaining elements of first half (if any)
    while (k<j)
        a[k++]=b[i++];
}

Here is the function to sort the array.


function mergesort(lo, hi) {
    if (lo<hi) {
        var m=(lo+hi)/2;
        mergesort(lo, m);
        mergesort(m+1, hi);
        merge(lo, m, hi);
    }
}