/
mergesort.js
46 lines (35 loc) · 930 Bytes
/
mergesort.js
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
function mergeSort(ar) {
if (ar.length === 1) return ar;
let half;
if (ar.length % 2 === 0)
half = ar.length / 2;
else
half = Math.floor(ar.length / 2) + 1;
const left = ar.slice(0, half);
const right = ar.slice(half);
return merge(mergeSort(left), mergeSort(right));
}
function merge(left, right) {
let ar = [];
let i = 0;
let j = 0;
while (i < left.length && j < right.length) {
if (left[i] <= right[j]) {
ar.push(left[i]);
i++;
} else {
ar.push(right[j]);
j++;
}
}
if (i === left.length)
ar = ar.concat(right.slice(j));
else
ar = ar.concat(left.slice(i));
return ar;
}
// const left = [-1, -1, 2, 99];
// const right = [-44, 0, 297];
// console.log(merge(left, right));
const numbers = [2, 99, -1, -1, 297, 0, -44];
console.log(mergeSort(numbers));