Add merge sort

kciter · kciter · commit 7a2f529053ed · 2016-05-22T18:12:36.000+09:00
diff --git a/algorithm/sorting/merge/basic/code.js b/algorithm/sorting/merge/basic/code.js
@@ -0,0 +1,76 @@
+tracer._print('original array = [' + D.join(', ') + ']');
+tracer._sleep(1000);
+tracer._pace(500);
+
+function mergeSort(start, end) {
+    if (Math.abs(end - start) <= 1) {
+      return [];
+    }
+    
+    var middle = Math.ceil((start + end) / 2);
+
+    mergeSort(start, middle);
+    mergeSort(middle, end);
+    
+    tracer._print('divide left[' + start + ', ' + (middle-1) + '], right[' + (middle) + ', ' + (end-1) + ']');
+
+    return mergeSort.merge(start, middle, end);
+}
+
+mergeSort.merge = function (start, middle, end) {
+    var left = Array();
+    var right = Array();
+
+    var leftSize = middle - start;
+    var rightSize = end - middle;
+    var maxSize = Math.max(leftSize, rightSize);
+    var size = end - start;
+    var i;
+
+    for (i = 0; i < maxSize; i++) {
+      if (i < leftSize) {
+        left.push(D[start + i]);
+        tracer._select(start + i);
+        tracer._print('insert value into left array[' + i +'] = ' + D[start + i]);
+      }
+      if (i < rightSize) {
+        right.push(D[middle + i]);
+        tracer._select(middle + i);
+        tracer._print('insert value into right array[' + i +'] = ' + D[middle + i]);
+      }
+    }
+    tracer._print('left array = [' + left.join(', ') + '],' + 'right array = [' + right.join(', ') + ']');
+    
+    i = 0;
+    while (i < size) {
+      if (left[0] && right[0]) {
+        if (left[0] > right[0]) {
+          D[start + i] = right.shift();
+          tracer._print('rewrite from right array[' + i + '] = ' + D[start+i]);
+        } else {
+          D[start + i] = left.shift();
+          tracer._print('rewrite from left array[' + i + '] = ' + D[start+i]);
+        }
+      } else if (left[0]) {
+        D[start + i] = left.shift();
+        tracer._print('rewrite from left array[' + i + '] = ' + D[start+i]);
+      } else {
+        D[start + i] = right.shift();
+        tracer._print('rewrite from right array[' + i + '] = ' + D[start+i]);
+      }
+      
+      tracer._deselect(start + i);
+      tracer._notify(start + i);
+      
+      i++;
+    }
+    
+    tempArray = Array();
+    for (i=start; i<end; i++) {
+        tempArray.push(D[i]);
+    }
+    tracer._print('merged array = [' + tempArray.join(', ') + ']');
+}
+
+mergeSort(0, D.length)
+tracer._print('sorted array = [' + D.join(', ') + ']');
diff --git a/algorithm/sorting/merge/basic/data.js b/algorithm/sorting/merge/basic/data.js
@@ -0,0 +1,3 @@
+var tracer = new Array1DTracer();
+var D = Array1D.random(15);
+tracer._setData(D);
diff --git a/algorithm/sorting/merge/desc.json b/algorithm/sorting/merge/desc.json
@@ -0,0 +1,13 @@
+{
+  "Quicksort": "In computer science, merge sort (also commonly spelled mergesort) is an efficient, general-purpose, comparison-based sorting algorithm. Most implementations produce a stable sort, which means that the implementation preserves the input order of equal elements in the sorted output. Mergesort is a divide and conquer algorithm that was invented by John von Neumann in 1945. A detailed description and analysis of bottom-up mergesort appeared in a report by Goldstine and Neumann as early as 1948.",
+  "Complexity": {
+    "time": "average O(n log n)",
+    "space": "worst O(n)"
+  },
+  "References": [
+    "<a href='https://en.wikipedia.org/wiki/Merge_sort'>Wikipedia</a>"
+  ],
+  "files": {
+    "basic": "Basic"
+  }
+}

Original file line number	Diff line number	Diff line change
`@@ -0,0 +1,3 @@`
	`1`	`+var tracer = new Array1DTracer();`
	`2`	`+var D = Array1D.random(15);`
	`3`	`+tracer._setData(D);`