1// Merge Sort Implentation (Recursive)
2
3function mergeSort (unsortedArray) {
4 if (unsortedArray.length <= 1) {
5 return unsortedArray;
6 }
7
8 const middle = Math.floor(unsortedArray.length / 2);
9
10 const left = unsortedArray.slice(0, middle);
11 const right = unsortedArray.slice(middle);
12
13 // Using recursion to combine the left and right
14 return merge(
15 mergeSort(left),
16 mergeSort(right)
17 );
18}
19
20function merge (left, right) {
21 let resultArray = [], leftIndex = 0, rightIndex = 0;
22
23 while (leftIndex < left.length && rightIndex < right.length) {
24 if (left[leftIndex] < right[rightIndex]) {
25 resultArray.push(left[leftIndex]);
26 leftIndex++;
27 } else {
28 resultArray.push(right[rightIndex]);
29 rightIndex++;
30 }
31 }
32
33 return resultArray
34 .concat(left.slice(leftIndex))
35 .concat(right.slice(rightIndex));
36}
1// Merge Sort (Recursive)
2function mergeSort (unsortedArray) {
3 // No need to sort the array if the array only has one element or empty
4 if (unsortedArray.length <= 1) {
5 return unsortedArray;
6 }
7 // In order to divide the array in half, we need to figure out the middle
8 const middle = Math.floor(unsortedArray.length / 2);
9
10 // This is where we will be dividing the array into left and right
11 const left = unsortedArray.slice(0, middle);
12 const right = unsortedArray.slice(middle);
13
14 // Using recursion to combine the left and right
15 return merge(
16 mergeSort(left), mergeSort(right)
17 );
18}
1function merge(left, right) {
2 const resultArray = []
3 let leftIndex = 0
4 let rightIndex = 0
5
6 while (leftIndex < left.length && rightIndex < right.length) {
7 if (left[leftIndex] < right[rightIndex]) {
8 resultArray.push(left[leftIndex])
9 leftIndex+=1
10 } else {
11 resultArray.push(right[rightIndex])
12 rightIndex+=1
13 }
14 }
15 return resultArray
16 .concat(left.slice(leftIndex))
17 .concat(right.slice(rightIndex))
18}
19function mergeSort(unsortedArray) {
20 if (unsortedArray.length <= 1) {
21 return unsortedArray;
22 }
23 const middle = Math.floor(unsortedArray.length / 2);
24 const left = unsortedArray.slice(0, middle);
25 const right = unsortedArray.slice(middle);
26 return merge(
27 mergeSort(left), mergeSort(right)
28 );
29}
30mergeSort([10, 9, 8, 7, 6, 5, 4, 3, 2, 1])
1function mergeSort(array, compare = (a, b) => a < b) {
2 if (array.length < 2) { return array; }
3
4 const middleIndex = Math.floor(array.length / 2);
5 const head = mergeSort(array.slice(0, middleIndex), compare);
6 const tail = mergeSort(array.slice(middleIndex), compare);
7
8 const orderedArray = [];
9 let tailIndex = 0;
10 for (const element of head) {
11 while(tailIndex < tail.length && compare(tail[tailIndex], element)) {
12 orderedArray.push(tail[tailIndex++]);
13 }
14 orderedArray.push(element)
15 }
16 if (tailIndex < tail.length) {
17 orderedArray.push(...tail.slice(tailIndex));
18 }
19
20 return orderedArray;
21}
1const merge = (left, right) => {
2 const resArr = [];
3 let leftIdx = 0;
4 let rightIdx = 0;
5
6 while (leftIdx < left.length && rightIdx < right.length) {
7 left[leftIdx] < right[rightIdx]
8 ? resArr.push(left[leftIdx++])
9 : resArr.push(right[rightIdx++]);
10 }
11 return [...resArr, ...left.slice(leftIdx), ...right.slice(rightIdx)];
12};
13
14const mergeSort = arr =>
15 arr.length <= 1
16 ? arr
17 : merge(
18 mergeSort(arr.slice(0, Math.floor(arr.length / 2))),
19 mergeSort(arr.slice(Math.floor(arr.length / 2)))
20 );