The Merge Sort Algorithm is a sorting algorithm that uses the Divide and conquer technique to sort the array elements in ascending or descending order. In this algorithm, we break our problem into sub-problems then we try to merge the solution of the sub-problem to get the solution of our main problem.
Working of Merge Sort Algorithm.
The merge Sort approach is entirely different than other sorting algorithms like Selection sort, Bubble sort, and Insertion sort where the time complexity of these algorithms is O(n^2) in the average case our Merge sort algorithm's time complexity is O(nlogn).
Here we divide the given unsorted array into two equal halves (if an array has an odd number of elements then one half will have more elements than the other half) then we apply some algorithm to sort these two equal halves and we merge these two halves in sorted order.
Now if you observe carefully, we have two tasks one is to sort the two halves and the next is to merge the two sorted sub-array in a bigger array but in sorted order. We are going to use Recursion to perform this dividing of the array into two equal parts because we will keep on diving the array until no further division is possible and while returning back we are going to perform the merge operation.
Lets us first understand how the merge operation is going to take place when we already have two sorted sub-array.
Let's say we named two sorted sub-array as the left sub-array (left[]), and the other as the right sub-array (right[]). Since all the elements of the given array, Arr[] are present either in the left sub-array or right sub-array so we will start picking the smallest element either from the left or right sub-array and start overwriting in the given Array Arr[]
.
Algorithm to Merge Two-Sorted Arrays:
Step 1: Get the size of the left subarray and right subarray.
Step 2: Declare three variables i, j, and k, and initialize them with 0.
Step 3: Run a while loop with the below condition to merge two sorted arrays:
while(i < left_subarray_size && j < right_subarray_size){ if(left[i] <= right[j]){ arr[k] = left[i]; k++; i++; } else{ arr[k] = right[j]; k++; j++; } }
Step 4: The above while loop condition will fail when we meet a condition where no elements are present to compare either in the left subarray or in the right subarray. In this case, we have picked all the elements of the other array and filled the rest of the position. We can run two different while loops for both left and right subarrays.
//copy the remaining elements from left subarray if any. while(i < left_subarray_size){ arr[k] = left[i]; i++; k++; } //copy the remaining elements from right subarray if any. while(j < right_subarray_size){ arr[k] = right[j]; j++; k++; }
Now after understanding the algorithm of merging two sorted arrays and combining them into a single larger sorted array. It is the right to understand the working of the Merge sort algorithm and then only you will understand why it was necessary to understand the above merging algorithm before.
Basically, Merge Sort is a recursive algorithm in which we continually divide the given unsorted array into equal two parts until it cannot further divide. We will get this case when there is only one element left or the array is empty and it is our base case of recursion. When we hit the base case and start returning we will start merging both sorted halves into a larger array until the entire array is merged. This is where we will use the above algorithm of merging two sorted arrays.
Steps to perform Merge Sort Algorithm.
Step 1: Call a recursive mergesort(arr[], l, r) with given array and one left variable and one right variable.
Step 2: If left >= right then we hit the base case and you need to return.
Step 3: If left < right then we have need to perform the below task.
Step 4: Find the middle to divide the array into equal halves.
- mid = left + (right - left)/2
Step 5: Call mergersort again on first half.
- mergesort(arr[], left, mid);
Step 6: Call mergersort again on second half.
- mergesort(arr[], mid+1, right);
Step 7: Call merge function to merge two sorted half together (as shown above).
- merge(arr[], left, mid, right);(alert-success)
C++ Code Implementation for Merge Sort Algorithm.
#include<iostream> using namespace std; //function to merge two sorted array void merge(int arr[], int left, int mid, int right){ int left_subarray_size = mid - left + 1; int right_subarray_size = right - mid; int leftArr[left_subarray_size]; int rightArr[right_subarray_size]; //copying data of left and right subarray from main array for(int i = 0; i < left_subarray_size; i++){ leftArr[i] = arr[left+i]; } for(int j = 0; j < right_subarray_size; j++){ rightArr[j] = arr[mid+j+1]; } int i = 0, j = 0, k = left; //Merging left and right sorted array into main array while(i < left_subarray_size && j < right_subarray_size){ if(leftArr[i] <= rightArr[j]){ arr[k] = leftArr[i]; k++; i++; } else{ arr[k] = rightArr[j]; k++; j++; } } //copy the remaining elements from left subarray. while(i < left_subarray_size){ arr[k] = leftArr[i]; i++; k++; } //copy the remaining elements from right subarray. while(j < right_subarray_size){ arr[k] = rightArr[j]; j++; k++; } } //MergeSort Recursive Function void mergeSort(int arr[], int left, int right){ if(left >= right) return; int mid = left + (right - left)/2; //Calling mergeSort recursively on both halves mergeSort(arr, left, mid); mergeSort(arr, mid+1, right); merge(arr, left, mid, right); }
int main(){ int arr[] = {2, 4, 1, 6, 8, 5, 3, 7}; int n = sizeof(arr)/sizeof(arr[0]); cout<<"Array before Sorting: "; for(int i = 0; i < n; i++){ cout<<arr[i]<<" "; } //Calling Merge Sort Function mergeSort(arr, 0, n-1); cout<<"\nArray after Sorting: "; for(int i = 0; i < n; i++){ cout<<arr[i]<<" "; } }
Array before Sorting: 2 4 1 6 8 5 3 7 Array after Sorting: 1 2 3 4 5 6 7 8
- Time complexity: O(NlogN)
- Space Complexity: O(N)
Trends is an amazing magazine Blogger theme that is easy to customize and change to fit your needs.