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])
1var array_length;
2/* to create MAX array */
3function heap_root(input, i) {
4 var left = 2 * i + 1;
5 var right = 2 * i + 2;
6 var max = i;
7
8 if (left < array_length && input[left] > input[max]) {
9 max = left;
10 }
11
12 if (right < array_length && input[right] > input[max]) {
13 max = right;
14 }
15
16 if (max != i) {
17 swap(input, i, max);
18 heap_root(input, max);
19 }
20}
21
22function swap(input, index_A, index_B) {
23 var temp = input[index_A];
24
25 input[index_A] = input[index_B];
26 input[index_B] = temp;
27}
28
29function heapSort(input) {
30
31 array_length = input.length;
32
33 for (var i = Math.floor(array_length / 2); i >= 0; i -= 1) {
34 heap_root(input, i);
35 }
36
37 for (i = input.length - 1; i > 0; i--) {
38 swap(input, 0, i);
39 array_length--;
40
41
42 heap_root(input, 0);
43 }
44}
45
46var arr = [3, 0, 2, 5, -1, 4, 1];
47heapSort(arr);
48console.log(arr);
49
50
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}
1/*
2 a[] is the array, p is starting index, that is 0,
3 and r is the last index of array.
4*/
5
6#include <stdio.h>
7
8// lets take a[5] = {32, 45, 67, 2, 7} as the array to be sorted.
9
10// merge sort function
11void mergeSort(int a[], int p, int r)
12{
13 int q;
14 if(p < r)
15 {
16 q = (p + r) / 2;
17 mergeSort(a, p, q);
18 mergeSort(a, q+1, r);
19 merge(a, p, q, r);
20 }
21}
22
23// function to merge the subarrays
24void merge(int a[], int p, int q, int r)
25{
26 int b[5]; //same size of a[]
27 int i, j, k;
28 k = 0;
29 i = p;
30 j = q + 1;
31 while(i <= q && j <= r)
32 {
33 if(a[i] < a[j])
34 {
35 b[k++] = a[i++]; // same as b[k]=a[i]; k++; i++;
36 }
37 else
38 {
39 b[k++] = a[j++];
40 }
41 }
42
43 while(i <= q)
44 {
45 b[k++] = a[i++];
46 }
47
48 while(j <= r)
49 {
50 b[k++] = a[j++];
51 }
52
53 for(i=r; i >= p; i--)
54 {
55 a[i] = b[--k]; // copying back the sorted list to a[]
56 }
57}
58
59// function to print the array
60void printArray(int a[], int size)
61{
62 int i;
63 for (i=0; i < size; i++)
64 {
65 printf("%d ", a[i]);
66 }
67 printf("\n");
68}
69
70int main()
71{
72 int arr[] = {32, 45, 67, 2, 7};
73 int len = sizeof(arr)/sizeof(arr[0]);
74
75 printf("Given array: \n");
76 printArray(arr, len);
77
78 // calling merge sort
79 mergeSort(arr, 0, len - 1);
80
81 printf("\nSorted array: \n");
82 printArray(arr, len);
83 return 0;
84}