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
Disclaimer: Don’t jump directly to the solution, try it out yourself first.
Solution :
Intuition:
-> Merge Sort is a divide and conquers 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 part of the array are sorted and merges both of them
- MergeSort() : This function divides the array into 2 parts . L to Miid and Mid+1 to R where,
L = leftmost index of array
R = rightmost index of array
Mid = Middle index of array
-> We recursively split the array, go from top-down until all sub-arrays size becomes 1.
Approach :
-> We will be creating 2 functions mergeSort() and merge()
-> In mergeSort(), we will divide the array around the middle element by making the recursive call :
1.mergeSort(arr,l,mid) 2. mergeSort(arr,mid+1,r)
where l = leftmost index of array, r = rightmost index of array , mid = middle index of array
-> In merge(), we will use a temporary array named temp. This will be used to store elements in sorted order from both the arrays which we divided.
->From the temporary array, we will return back the elements in the original array.
-> Now , let i = leftmost index of array, j = mid+1 index of array , f = leftmost index of array ( this index will be used to store elements in the original array )
-> While i<= mid && j <= r , we will store elements from both the parts in temporary array in sorted manner
-> Finally will transfer all elements from the temporary array to the original array.
-> The red number shows an order of the steps in recursion calls
Code:
C++ Code
#include <bits/stdc++.h>
using namespace std ;
class Solution {
public:
void merge(int arr[], int l, int mid, int r)
{
int i = l ; // starting index of left half of arr
int j = mid + 1; // starting index of right half of arr
int f = l ; // index used to transfer elements in temporary array
int temp[100000] ; // temporary array
//storing elements in the temporary array in a sorted manner//
while (i <= mid && j <= r) {
if (arr[i] < arr[j]) {
temp[f] = arr[i] ;
i++ ;
}
else {
temp[f] = arr[j] ;
j++ ;
}
f++ ;
}
// if elements on the left half are still left //
if (i > mid) {
while (j <= r) {
temp[f] = arr[j] ;
f++ ; j++ ;
}
}
else {
// if elements on the right half are still left //
while (i <= mid) {
temp[f] = arr[i] ;
f++ ; i++ ;
}
}
// transfering all elements from temporary to arr //
for (int f = l ; f <= r; f++) {
arr[f] = temp[f] ;
}
}
void mergeSort(int arr[], int l, int r)
{
if (l < r) {
int mid = (l + r) / 2 ;
mergeSort(arr, l, mid) ; // left half
mergeSort(arr, mid + 1, r) ; // right half
merge(arr, l, mid, r) ; // merging sorted halves
}
}
};
int main() {
int arr[] = {9, 4, 7, 6, 3, 1, 5} ;
int n = 7;
Solution obj ;
cout << "Before Sorting Array: "<<endl;
for (int i = 0; i < n; i++) {
cout << arr[i] << " " ;
}
cout<<endl;
obj.mergeSort(arr, 0, n - 1);
cout << "After Sorting Array: "<<endl;
for (int i = 0; i < n; i++) {
cout << arr[i] << " " ;
}
return 0 ;
}
Output:
Before Sorting Array:
9 4 7 6 3 1 5
After Sorting Array:
1 3 4 5 6 7 9
Time complexity: O(nlogn)
Reason: At each step, we divide the whole array, for that logn and we assume n steps are taken to get sorted array, so overall time complexity will be nlogn
Space complexity: O(n)
Reason: We are using a temporary array to store elements in sorted order.
Auxiliary Space Complexity: O(n)
Java Code
import java.util.*;
class MergeSortClass {
void mergeSort(int arr[], int l, int r) {
if (l < r) {
int mid = (l + r) / 2;
mergeSort(arr, l, mid); // left half
mergeSort(arr, mid + 1, r); // right half
merge(arr, l, mid, r); // merging sorted halves
}
}
void merge(int arr[], int l, int mid, int r) {
int i = l; // starting index of left half of arr
int j = mid + 1; // starting index of right half of arr
int f = l; // index used to transfer elements in temporary array
int temp[] = new int[100000]; // temporary array
// storing elements in the temporary array in a sorted manner//
while (i <= mid && j <= r) {
if (arr[i] < arr[j]) {
temp[f] = arr[i];
i++;
} else {
temp[f] = arr[j];
j++;
}
f++;
}
// if elements on the left half are still left //
if (i > mid) {
while (j <= r) {
temp[f] = arr[j];
f++;
j++;
}
} else {
// if elements on the right half are still left //
while (i <= mid) {
temp[f] = arr[i];
f++;
i++;
}
}
// transfering all elements from temporary to arr //
for (f = l; f <= r; f++) {
arr[f] = temp[f];
}
}
}
class Solution {
public static void main(String args[]) {
Scanner sc = new Scanner(System.in);
int n = 7;
int arr[] = { 9, 4, 7, 6, 3, 1, 5 };
System.out.println("Before sorting array: ");
for (int i = 0; i < n; i++) {
System.out.print(arr[i] + " ");
}
System.out.println();
MergeSortClass obj = new MergeSortClass();
obj.mergeSort(arr, 0, n - 1);
System.out.println("After sorting array: ");
for (int i = 0; i < n; i++) {
System.out.print(arr[i] + " ");
}
}
}
Output:
Before Sorting Array:
9 4 7 6 3 1 5
After Sorting Array:
1 3 4 5 6 7 9
Time complexity: O(nlogn)
Reason: At each step, we divide the whole array, for that logn and we assume n steps are taken to get sorted array, so overall time complexity will be nlogn
Space complexity: O(n)
Reason: We are using a temporary array to store elements in sorted order.
Auxiliary Space Complexity: O(n)
Special thanks to Shreyas Vishwakarma for contributing to this article on takeUforward. If you also wish to share your knowledge with the takeUforward fam, please check out this article