Merge Sort

Merge sort is a commonly asked sorting question for sorting elements of an array. So basically, in merge sort we aim to split the list into smaller parts and then sort each part of the list separately. Once all the parts are sorted we merge the list which eventually makes it a sorted list.

The Problem Statement is as follows:

Given an array of N integers, sort the elements of the array using the Merge Sort algorithm.

Example:

Input: N = 7, array[] = {1,15,5,7,0,12,45}

Output: 0,1,5,7,12,15,45

Code:

Explanation:

1.     Merge Sort Function (mergeSort): This function is used to sort the given array using the merge sort algorithm.

·         Initially it divides the array into halves recursively until each half contains only one element or becomes empty.

·         Then, it merges these halves back together and gives us the sorted array.

2.     Merging Function (merge): This function merges two sorted halves of an array into a single sorted array.

·        It creates a temporary array to store the sorted elements.

·        Then, it compares elements from both the halves. The smaller elements get added first into our temporary array.

·        If there are any remaining elements in either half, they directly get added to the temporary array.

·        Finally the sorted elements get copied from the temporary array back to the original array.

Time complexity: O(nlogn) 

Space complexity: O(n)