merge sort complexity analysis code example

Example 1: merge sort

# 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 A

Example 2: merge sort algorithm

/*  
    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;
}