Merge sort is the sorting technique that follows the divide and conquers strategy.
It is very much similar to the quick sort algorithm as it also prefers the divide and conquers method to sort the elements. It is one of the most prevalent and efficient sorting algorithms. It splits the provided array into two halves, then sorts them and combines them.
- Merge Sort Algorithm
- Working of Merge Sort Algorithm
- Merge Sort Complexity
- Time Complexity of Merge Sort Algorithm
- Space Complexity of Merge Sort Algorithm
Now, let’s see the algorithm of merge sort.
Merge Sort Algorithm
In the below algorithm, ar is the given array, start is the starting element, and finish is the last component of the array.
- MERGE_SORT(ar, start, finish)
- if start< finish
- set mid = (start + finish)/2
- MERGE_SORT(ar, start, mid)
- MERGE_SORT(ar, mid + 1, finish)
- MERGE (ar, start, mid, finish)
- finish of if
- FINISH MERGE_SORT
Working of Merge Sort Algorithm
To understand the working of the merge sort algorithm, we are considering an unsorted list of arrays.
Let the components of the array are –
The given array will initially be divided into two parts in accordance with the merge sort. The list is repeatedly split into two equal pieces in the merge sort algorithm until it can no longer be split.
There are a total of eight elements in the array below, which has been separated into four array sizes (each).
Now divide these two arrays once more into two sections. These arrays are 4 bytes in size. We’ll divide them into two equal pieces.
To get the final value that we can’t split any further, we shall split these arrays once more.
Now, combine them exactly as we did when we separated them.
Merging involves comparing the list’s elements first, after which they are combined into another list of sorted arrays.
Therefore, compare 11 and 30 first since they both have sorted positions. Then, after comparing 24 and 7, order the two values in the array of two by placing 7 before 24. Then order them and place 16 first, then 31 after comparing 31 and 16. Compare 39 and 41 after that, then arrange them in order.
In the subsequent iteration, compare the arrays holding the two data values and combine them into a single array of found values in sorted order.
The arrays are finally combined at this point. The array will now appear as follows:
Now, the array is completely sorted.
Merge Sort Complexity
1. Time Complexity of Merge Sort Algorithm
| Case | Time Complexity of Merge Sort |
|---|---|
| Best Case | O(n*logn) |
| Average Case | O(n*logn) |
| Worst Case | O(n*logn) |
2. Space Complexity of Merge Sort Algorithm
| Space Complexity of Merge Sort Algorithm | O(n)6 |
|---|
Keep learning and stay tuned to get the latest updates on GATE Exam along with GATE Eligibility Criteria, GATE 2023, GATE Admit Card, GATE Syllabus for CSE (Computer Science Engineering), GATE CSE Notes, GATE CSE Question Paper, and more.
Also Explore,
