forked from algorithm-visualizer/algorithm-visualizer
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathcode.js
More file actions
76 lines (63 loc) · 2.2 KB
/
code.js
File metadata and controls
76 lines (63 loc) · 2.2 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
69
70
71
72
73
74
75
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(', ') + ']');