forked from algorithm-visualizer/algorithm-visualizer
-
Notifications
You must be signed in to change notification settings - Fork 1
Expand file tree
/
Copy pathcode.js
More file actions
68 lines (59 loc) · 2.25 KB
/
code.js
File metadata and controls
68 lines (59 loc) · 2.25 KB
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
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) {
const leftSize = middle - start;
const rightSize = end - middle;
const maxSize = Math.max(leftSize, rightSize);
const size = end - start;
var left = [];
var right = [];
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++;
}
var tempArray = [];
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(', ') + ']');