merge sort

seunzone · seunzone · commit 8aecf0b558ca · 2017-09-05T14:38:50.000+01:00
diff --git a/algorithms/sorting_algo/mergesort.js b/algorithms/sorting_algo/mergesort.js
@@ -0,0 +1,40 @@
+// The Merge sort algorithm
+
+// Definition
+
+// Merge sort is a divide and conquer algorithm. 
+// Conceptually, a Merge sort works as follows: 
+// 1) Divide the unsorted list into n sublists, each containing 1 element 
+// (a list of 1 element is considered sorted), 
+// 2) Repeatedly merge sublists to produce new sorted sublists until there is only 1 sublist remaining. 
+// This will be the sorted list. From Wikipedia
+
+// array to sort
+var array = [9, 2, 5, 6, 4, 3, 7, 10, 1, 8];
+
+// top-down implementation
+function mergeSortTopDown(array) {
+  if(array.length < 2) {
+    return array;
+  }
+
+  var middle = Math.floor(array.length / 2);
+  var left = array.slice(0, middle);
+  var right = array.slice(middle);
+
+  return mergeTopDown(mergeSortTopDown(left), mergeSortTopDown(right));
+}
+function mergeTopDown(left, right) {
+  var array = [];
+
+  while(left.length && right.length) {
+    if(left[0] < right[0]) {
+      array.push(left.shift());
+    } else {
+      array.push(right.shift());
+    }
+  }
+  return array.concat(left.slice()).concat(right.slice());
+}
+
+console.log(mergeSortTopDown(array.slice())); // => [ 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 ]
diff --git a/algorithms/sorting_algo/quicksort.js b/algorithms/sorting_algo/quicksort.js
@@ -33,61 +33,3 @@ function quicksortBasic(array) {
 
 console.log(quicksortBasic(array.slice())); // => [ 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 ]
 
-// swap function helper
-function swap(array, i, j) {
-  var temp = array[i];
-  array[i] = array[j];
-  array[j] = temp;
-}
-
-// classic implementation (with Hoare or Lomuto partition scheme, you can comment either one method or the other to see the difference)
-function quicksort(array, left, right) {
-  left = left || 0;
-  right = right || array.length - 1;
-
-  // var pivot = partitionLomuto(array, left, right); // you can play with both partition
-  var pivot = partitionHoare(array, left, right); // you can play with both partition
-
-  if(left < pivot - 1) {
-    quicksort(array, left, pivot - 1);
-  }
-  if(right > pivot) {
-    quicksort(array, pivot, right);
-  }
-  return array;
-}
-// Lomuto partition scheme, it is less efficient than the Hoare partition scheme
-function partitionLomuto(array, left, right) {
-  var pivot = right;
-  var i = left;
-
-  for(var j = left; j < right; j++) {
-    if(array[j] <= array[pivot]) {
-      swap(array, i , j);
-      i = i + 1;
-    }
-  }
-  swap(array, i, j);
-  return i;
-}
-// Hoare partition scheme, it is more efficient than the Lomuto partition scheme because it does three times fewer swaps on average
-function partitionHoare(array, left, right) {
-  var pivot = Math.floor((left + right) / 2 );
-
-  while(left <= right) {
-    while(array[left] < array[pivot]) {
-      left++;
-    }
-    while(array[right] > array[pivot]) {
-      right--;
-    }
-    if(left <= right) {
-      swap(array, left, right);
-      left++;
-      right--;
-    }
-  }
-  return left;
-}
-
-console.log(quicksort(array.slice())); // => [ 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 ]
