Merge Sort Implementation

var merge = function(array, p, q, r) { // This code has been purposefully obfuscated, // as you'll write it yourself in next challenge. var a=[],b=[],c=p,d,e; for(d=0;c<=q;d++,c++){ a[d]=array[c]; } for(e=0;c<=r;e++,c++){ b[e]=array[c]; } c=p; for(e=d=0;d<a.length&&e<b.length;){ if(a[d]<b[e]){ array[c]=a[d];d++; } else{ array[c]=b[e]; e++; } c++; } for(;d<a.length;){ array[c]=a[d]; d++; c++; } for(;e<b.length;){ array[c]=b[e]; e++; c++; } }; // 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); } };

Linear time merging

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 < lowHalf.length && j < highHalf.length){ if(lowHalf[i] < highHalf[j]){ array[k] = lowHalf[i]; i++; } 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 < lowHalf.length){ array[k] = lowHalf[i]; i++; k++; } while(j < highHalf.length){ array[k] = highHalf[j]; j++; k++; } };

C implementation of Merge

int left_length = m - l + 1; int right_length = r - m; int temp_left[left_length]; int temp_right[right_length]; int i, j, k; for (int i = 0; i < left_length; i++) temp_left[i] = a[l + i]; for (int i = 0; i < right_length; i++) temp_right[i] = a[m + 1 + i]; for (i = 0, j = 0, k = l; k <= r; k++) { if ((i < left_length) && (j >= right_length || temp_left[i] <= temp_right[j])) { a[k] = temp_left[i]; i++; } else { a[k] = temp_right[j]; j++; } }