# 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

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 :

1. 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
2. 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 ; // 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; // 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)