merge sort

/*  
    a[] is the array, p is starting index, that is 0, 
    and r is the last index of array. 
*/

#include <stdio.h>

// lets take a[5] = {32, 45, 67, 2, 7} as the array to be sorted.

// merge sort function
void mergeSort(int a[], int p, int r)
{
    int q;
    if(p < r)
    {
        q = (p + r) / 2;
        mergeSort(a, p, q);
        mergeSort(a, q+1, r);
        merge(a, p, q, r);
    }
}

// function to merge the subarrays
void merge(int a[], int p, int q, int r)
{
    int b[5];   //same size of a[]
    int i, j, k;
    k = 0;
    i = p;
    j = q + 1;
    while(i <= q && j <= r)
    {
        if(a[i] < a[j])
        {
            b[k++] = a[i++];    // same as b[k]=a[i]; k++; i++;
        }
        else
        {
            b[k++] = a[j++];
        }
    }
  
    while(i <= q)
    {
        b[k++] = a[i++];
    }
  
    while(j <= r)
    {
        b[k++] = a[j++];
    }
  
    for(i=r; i >= p; i--)
    {
        a[i] = b[--k];  // copying back the sorted list to a[]
    } 
}

// function to print the array
void printArray(int a[], int size)
{
    int i;
    for (i=0; i < size; i++)
    {
        printf("%d ", a[i]);
    }
    printf("\n");
}
 
int main()
{
    int arr[] = {32, 45, 67, 2, 7};
    int len = sizeof(arr)/sizeof(arr[0]);
 
    printf("Given array: \n");
    printArray(arr, len);
    
    // calling merge sort
    mergeSort(arr, 0, len - 1);
 
    printf("\nSorted array: \n");
    printArray(arr, len);
    return 0;
}// @see https://www.youtube.com/watch?v=es2T6KY45cA&vl=en
// @see https://www.cs.usfca.edu/~galles/visualization/ComparisonSort.html

function merge(list, start, midpoint, end) {
    const left = list.slice(start, midpoint);
    const right = list.slice(midpoint, end);
    for (let topLeft = 0, topRight = 0, i = start; i < end; i += 1) {
        if (topLeft >= left.length) {
            list[i] = right[topRight++];
        } else if (topRight >= right.length) {
            list[i] = left[topLeft++];
        } else if (left[topLeft] < right[topRight]) {
            list[i] = left[topLeft++];
        } else {
            list[i] = right[topRight++];
        }
    }
}

function mergesort(list, start = 0, end = undefined) {
    if (end === undefined) {
        end = list.length;
    }
    if (end - start > 1) {
        const midpoint = ((end + start) / 2) >> 0;
        mergesort(list, start, midpoint);
        mergesort(list, midpoint, end);
        merge(list, start, midpoint, end);
    }
    return list;
}

mergesort([4, 7, 2, 6, 4, 1, 8, 3]);# Python3 recursive merge sort algorithm -> O(n*log(n))
def merge_sort(A):
    def merge(l, r):
        i = j = 0
        n = []  # merging container
        while i < len(l) or j < len(r):

            # if no more elements to the right,
            # add remaining left elements
            if i == len(l):
                n.extend(r[j:])
                break

            # if no more elements to the left,
            # add remaining right elements
            if j == len(r):
                n.extend(l[i:])
                break

            # if elements left on both sides,
            # add smaller element
            a, b = l[i], r[j]
            if a < b:
                n.append(a)
                i += 1
            else:
                n.append(b)
                j += 1

        return n

    # divide list down to single-elements
    s = len(A)
    if s > 1:
        s //= 2
        l = merge_sort(A[:s])  # split left
        r = merge_sort(A[s:])  # split right
        return merge(l, r)  # merge sides in order
    else:
        return Adef merge_sort(arr):
    if len(arr) > 1:
        middle = len(arr) // 2
        left = arr[:middle]
        right = arr[middle:]

        merge_sort(left)
        merge_sort(right)

        i = len(arr) - 1
        while i >= 0:
            if left and right:
                if left[-1] >= right[-1]:
                    arr[i] = left.pop()
                else:
                    arr[i] = right.pop()
            else:
                arr[i] = left.pop() if left else right.pop()
            i -= 1
    return arr