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