Merge Sort

Merge Sort is a divide-and-conquer algorithm that was invented by John von Neumann in 1945. It works by recursively splitting the array into halves until each sub-array contains a single element, and then merging those sub-arrays back together in sorted order.

#include<stdio.h>
void mergeSort(int[], int, int);
int main(){
    int n, arr[50];
    printf("Enter the number of elements: ");
    scanf("%d",&n);
    printf("Enter %d elements: ",n);
    for(int i=0;i<n;i++){
        scanf("%d",&arr[i]);
    }
    mergeSort(arr, 0, n-1);
    printf("Sorted array: ");
    for(int i=0;i<n;i++){
        printf("%d ",arr[i]);
    }
    return 0;
}

void mergeSort(int arr[], int left, int right){
    int mid, i, j, k, temp[50];
    if(left<right){
        mid = (left+right)/2;
        mergeSort(arr, left, mid);
        mergeSort(arr, mid+1, right);
        i = left;
        j = mid+1;
        k = left;
        while(i<=mid && j<=right){
            if(arr[i]<=arr[j]){
                temp[k++] = arr[i++];
            }else{
                temp[k++] = arr[j++];
            }
        }
        while(i<=mid){
            temp[k++] = arr[i++];
        }
        while(j<=right){
            temp[k++] = arr[j++];
        }
        for(i=left;i<=right;i++){
            arr[i] = temp[i];
        }
    }
}

Sample Input and Output:
Enter the number of elements: 7
Enter 7 elements: 6 3 12 9 15 21 18
Sorted array: 3 6 9 12 15 18 21