Skip to content

Instantly share code, notes, and snippets.

@alpgul
Last active March 23, 2018 13:37
Show Gist options
  • Save alpgul/b6c24f4bd650af0e24ed415968681347 to your computer and use it in GitHub Desktop.
Save alpgul/b6c24f4bd650af0e24ed415968681347 to your computer and use it in GitHub Desktop.
Merge Sort with Javascript
/*
Best Case:n*logn
Average Case:n*logn
Worst Case:n*logn
Space Complexity:N
*/
(function(){
let comparison=0;
let arr2=[28, 31, 43, 97, 49, 11, 33, 71, 41, 80, 86, 38, 53, 54, 7, 67, 96, 52, 29, 25, 56, 77, 73, 42, 62, 84, 21, 68, 2, 44, 9, 94, 66, 78, 6, 57, 20, 89, 1, 55, 65, 85, 51, 23, 70, 32, 12, 27, 18, 90, 4, 82, 5, 35, 58, 69, 22, 83, 37, 61, 79, 34, 81, 30, 72, 95, 91, 48, 88, 46, 3, 26, 60, 39, 17, 24, 74, 99, 10, 16, 87, 98, 76, 13, 36, 45, 59, 100, 50, 93, 19, 75, 92, 40, 8, 47, 14, 15, 63, 64];
let arr=[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 80, 81, 82, 83, 84, 85, 86, 87, 88, 89, 90, 91, 92, 93, 94, 95, 96, 97, 98, 99, 100];
function merge(l_array,r_array){
let left_end=l_array.length;
let right_end=r_array.length;
let left=0,right=0,temp=0;
let temp_array=[];
while(left<left_end && right<right_end){
comparison++;
if(l_array[left]<=r_array[right]){
temp_array[temp] = l_array[left];
temp++;
left++;
}
else{
temp_array[temp]=r_array[right];
right++;
temp++;
}
}
while (left <left_end)
{
comparison++;
temp_array[temp] = l_array[left];
left++;
temp++;
}
while (right < right_end)
{
comparison++;
temp_array[temp] = r_array[right];
right++;
temp++;
}
return temp_array;
}
function sort(array){
comparison++;
let n=array.length;
if ( n == 1 ) return array;
let left_array=array.slice(0,n/2);
let right_array=array.slice(n/2);
left_array=sort(left_array);
right_array=sort(right_array);
return merge(left_array, right_array);
}
function Merge_sort(A){
var start = Date.now();
A = sort(A);
var end = Date.now();
var elapsed = end - start;
console.log("Elapsed Time:"+elapsed);
console.log("Total comparison:"+comparison);
comparison=0;
return A;
}
Merge_sort(arr2);//Total comparison:871
console.log(Merge_sort(arr));
})();
@alpgul
Copy link
Author

alpgul commented Mar 23, 2018

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment