Merge Sort Algorithm
Problem
Given an array of size n, sort the array using Merge Sort.
Examples:
Example 1:
Input: N=5, arr[]=[4,2,1,6,7]
Output: 1,2,4,6,7
Example 2:
Input: N=7, arr[]=[3,2,8,5,1,4,23]
Output: 1,2,3,4,5,8,23
Solution
Intuition
- Merge Sort is a divide and conquer algorithm, it divides the given array into equal parts and then merges the 2 sorted parts.
- There are 2 main functions:
- merge(): This function is used to merge the 2 halves of the array. It assumes that both parts of the array are sorted and merges both of them.
- mergeSort(): This function divides the array into 2 parts: low to mid and mid+1 to high where,
low = leftmost index of the array
high = rightmost index of the array
mid = Middle index of the array
- We recursively split the array, and go from top-down until all sub-arrays size becomes 1.
Approach
- We will be creating 2 functions mergeSort() and merge().
- mergeSort(arr, low, high):
- Base case: If low is greater than or equal to high, return.
- Calculate mid = low + (high - low) / 2
- Call mergeSort for first half: mergeSort(arr, low, mid)
- Call mergeSort for second half: mergeSort(arr, mid + 1, high)
- Merge the two halves: merge(arr, low, mid, high)
- merge(arr, low, mid, high):
- Create temporary arrays to store the two halves
- Copy data to temporary arrays
- Merge the temporary arrays back into arr[low..high]
Complexity Analysis
- Time Complexity: O(n log n) - The algorithm divides the array into two halves and takes linear time to merge them.
- Space Complexity: O(n) - We need additional space for the temporary arrays during merging.
Implementation
CPP
Run your code to see output here