merge sort javascript

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}