-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathMergeSort.js
More file actions
55 lines (44 loc) · 1.73 KB
/
MergeSort.js
File metadata and controls
55 lines (44 loc) · 1.73 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
const numbers = [99, 44, 6, 2, 1, 5, 63, 87, 283, 4, 0];
// The `mergeSort()` function takes an array as input and returns the sorted array.
// The function works by recursively sorting the left and right halves of the array.
function mergeSort(array) {
// If the array is empty or has only one element, it is already sorted.
if (array.length <= 1) {
return array;
}
// Calculate the middle index of the array.
const mid = Math.floor(array.length / 2);
// Recursively sort the left and right halves of the array.
const left = mergeSort(array.slice(0, mid));
const right = mergeSort(array.slice(mid));
// Merge the sorted left and right halves of the array.
return merge(left, right);
}
// The `merge()` function takes two sorted arrays as input and returns the merged sorted array.
// The function works by iterating through the two sorted arrays, adding the smaller element from each array to the merged array.
function merge(left, right) {
// Create a new array to store the merged sorted elements.
const merged = [];
// Declare two indexes to iterate through the left and right arrays.
let i = 0;
let j = 0;
// Iterate through the left and right arrays, adding the smaller element from each array to the merged array.
while (i < left.length && j < right.length) {
if (left[i] < right[j]) {
merged.push(left[i]);
i++;
} else {
merged.push(right[j]);
j++;
}
}
// Add the remaining elements from the left and right arrays to the merged array.
merged.push(...left.slice(i));
merged.push(...right.slice(j));
// Return the merged sorted array.
return merged;
}
// Sort the array using merge sort.
mergeSort(numbers);
// Print the sorted array to the console.
console.log(numbers);