In this article, we will study what is sorting and its importance in practical life. Further, we will learn merge sort and its technique using the divide and conquer approach. Also, we will learn the merge sort algorithm using an example along with its python code, and lastly the applications of merge sort in detail. So, let's get started!
What is Sorting And How It Is Important?
Sorting is a technique to rearrange the collection of data into a specific order. Just imagine trying to find a meaning of the word in the dictionary, which is not ordered in alphabetical sequence! It's really time-consuming and not at all an effective process. Therefore, we use certain sorting algorithms which help us to order the collection of data whether it’s worded in a dictionary or phone numbers on your mobile. There are many sorting algorithms possible to sort the data like the bubble sort, insertion sort, merge sort, quick sort, counting sort, etc. All these algorithms have their own techniques to sort the data, along with some advantages and disadvantages. In this article, our focus is on what is merge sort, and its algorithm to sort the large collection of data efficiently and in a very short amount of time.
What is Merge Sort?
Merge sort is one of the most important sorting algorithms based on the divide and conquer technique. Merge sort is very popular for its efficiency to sort the data in a small amount of time. It is one of the best examples of applications for divide and conquers algorithms. Basically, the principle working of merge sort is that it divides the list of data into two halves and again calls these subparts to further divide it into two halves. It keeps repeating the process until each subpart of the list contains only one element. Later, it will join these sub-parts of one element each into two elements by sorting them. Again, the subpart containing two elements will be joined with the other two elements after sorting. This process keeps repeating by calling the function recursively until we get the final sorted list of elements.
Algorithm for Merge Sort
The divide and conquer approach to sort n numbers using merge sort consists of separating the array T into two parts where the sizes are almost the same. These two parts are sorted by recursive calls and then merged with the solution of each part while preserving the order. The algorithm considers two temporary arrays U and V, into which the original array T is divided. When the number of elements to be sorted is small, a relatively simple algorithm is used. ‘mergeSort’ separates the instance into two halves sized sub instances, solves them recursively, and then combines the two sorted half arrays to obtain the solution to the original instance.
Merge(U[1,....,m+1], V[1,....,n+1], T[1,....,m+n]) i,j <- 1 U[m+1], V[n+1] <- infinite for k <- 1 to m+n do if U[i] < V[j] then T[k] <- U[i]; i <- i + 1 else T[k] <- V[j]; j <- j + 1 mergeSort(T[1,....,n]) if n is sufficiently small then insert(T) else array U[1,...1+(n/2)], V[1,....1+(n/2)] U[1,...(n/2)] <- T[1,...(n/2)] V[1,...(n/2)] <- T[(n/2)+1,...n] mergeSort(U[1,...(n/2)]) mergeSort(V[1,...(n/2)]) Merge(U, V, T)
Example
Here we take the given unsorted list of elements.
We divide it into two halves as given below
We keep dividing it until the subpart of the list consists of only one element
Later, we will combine the two elements in the given sorted manner
Again, we will combine the two lists of two elements and convert them into a list of four elements after sorting. We will keep repeating the process until we find the final sorted sequence of the array
The final sorted sequence of data is as given
Python Program For Merge Sort
def mergeSort(arr): if len(arr) > 1: a = len(arr)//2 l = arr[:a] r = arr[a:] # Sort the two halves mergeSort(l) mergeSort(r) b = c = d = 0 while b < len(l) and c < len(r): if l[b] < r[c]: arr[d] = l[b] b += 1 else: arr[d] = r[c] c += 1 d += 1 while b < len(l): arr[d] = l[b] b += 1 d += 1 while c < len(r): arr[d] = r[c] c += 1 d += 1 def printList(arr): for i in range(len(arr)): print(arr[i], end=" ") print() # Driver program if __name__ == '__main__': arr = [0,1,3,5,7,9,2,4,6,8] mergeSort(arr) print("Sorted array is: ") printList(arr)
Output
0,1,2,3,4,5,6,7,8,9
Time and Space Complexity
The running time complexity for best case, worst case, and average-case scenario is O(n*log n) where n is the number of elements to be sorted. The space complexity of the algorithm is O(n) where we need an array of size n to place the sorted element.
Advantages Of Merge Sort
- Merge sort allows sorting large data set easily
- Merge sort can access data in sequence, hence the need for random access is low
- Merge sort is a stable sorting algorithm
- It has the same running time complexity irrespective of case scenarios
Disadvantages Of Merge Sort
- It requires an array of the same size as the original list to store the final sorted array which consumes the large memory space
- It is slower when it comes to sorting smaller data sets
Applications
- Merge sort is used in e-commerce application
- Merge sort is the best way to sort the linked list in comparison to another sorting algorithm
- Merge sort is used in internal and external sorting
- It is used in organizing MP3 library
- It is used to display Google PageRank results
- Merge sort is widely used in inversion count problem
Conclusion
As merge sort has its own importance to sort the data fast and effectively, it is the most important sorting algorithm among all others. Merge sort is applied as a basic strategy in every possible practical application in our day-to-day life and hence here we have mentioned the working and example of merge sort with its advantages as well as disadvantages for your clear understanding.
