Sorting and Searching algorithms like insertion sort, selection sort, merge sort is essential to learn as a programmer because these form the base of any programmer. As a programmer, you have to deal with large amounts of data from time to time. This data needs to be sorted in a logical manner. A sorting algorithm is used to rearrange a given list or an array of elements in a defined order, either increasing or decreasing. In this section, we’re going to cover the implementation of the Merge Sort Algorithm with examples in Data Structures and Algorithm category using Python. Merge sort algorithm is a sorting algorithm that is used to sort a list or an array in ascending or descending order based on the user preference. It is completely based on the concept of “divide and conquer”. It first divides the array into equal halves and then merges them back again in a sorted manner.
For example, if we have the input list/array like this :
3, 1, 4, 1, 5, 9, 2, 6, 5, 4
Then after implementing this algorithm the output will be like this:
1, 1, 2, 3, 4, 4, 5, 5, 6, 9
Table of Contents :
- How does the Merge Sort algorithm works?
- Features of the Algorithm.
- Stepwise algorithm and Pseudocode for Merge Sort.
- Merge Sort Implementation in Python [Complete Code].
- Merge Sort Implementation in C++ [Complete Code].
- Time complexity [Best-case, Average-case, Worst-case].
- Space Complexity of Merge Sort.
- Applications of Merge Sort Algorithm.
How Merge Sort Algorithm Works?
This algorithm is one of the most efficient techniques to sort an array and it is implemented using the divide and conquer approach.
- The array or list is divide into half and then the halves are further divided into halves. This process is repeated recursively till the size of the array is either 1 or 0.
- By dividing we break the problem into subproblems. Until we are left with only one element. And a single element is already sorted.
- Now we apply the conquer technique by merging two sub-arrays into a single array and repeat this process until all the elements are combined and the array is sorted.
Let’s understand this with the help of an example to make it crystal clear.
Consider the given array of elements: 70, 50, 30, 10, 20, 40, 60.
We know the algorithm first divide the array into two halves:
The divided halves are further divided into halves, keeping the sequence as it is. No sorting takes place at this point:
The further division takes place until we are left with single elements:
Now that the list has been broken down into single element list we start merging it. We compare elements of one list with the elements of another list and merge them into a new list in a sorted manner.
From single elements now we have lists that contain two elements. We further merge this list by comparing elements of both lists one by one and inserting them into a new list that is sorted.
The above same process is repeated until we are left with only one list containing all the elements of the initial list we began with. This is the final sorted list that we want.
So the final output from the above example will be a sorted list with elements arranged in ascending order as 10, 20, 30, 40, 50, 60, 70.
Features of Merge Sort Algorithm
- In Merge sort, is not an in-place sorting algorithm because it does require n different array or data structure to perform its operations.
- This algorithm is also a stable sorting algorithm just like the bubble sort, insertion sort, count sort, etc as any two-element with the same key appears in the same order in the sorted array as they appear in the initially given array. Merge sort maintains the relative ordering.
- Just like quick sort merge sort is another sorting algorithm based on the divide and conquer approach.
- But unlike quick sort Merge sort is not an adaptive sorting algorithm as the time complexity of Merge sort does not depends on the initial input sequence of the given array.
- The divide and conquer technique used by merge sort makes it convenient for parallel processing.
Merge sort work on the principle that keeps on dividing the list into halves until no further division can take place. In the end, a list will contain only one element, and if the list contains only one element then it is sorted by default. Then merge sort combine these smaller sorted lists into a single sorted list. The algorithm goes as follows:
Step 1: if there is only one element left in the array, then it is already sorted, return.
Step 2: Divide the array recursively into halves until there can be no more divisions possible.
Step 3: Merge the smaller arrays into one array keeping it sorted in order.
- Declare two variables left and right to mark the extreme indices of the array.
- Left will be equal to 0 and the value of right will be equal to size-1, where size is the length of the given unsorted array.
- Find the middle point of this array by applying mid = (left + right) / 2.
- Call the function mergeSort by passing the arguments as (left, mid) and (mid + 1, rear).
- The above steps will repeat till left < right.
- Then we will call the merge function on two sub-arrays.
Merge Sort Program in Python
#Code by copyassignment.com #Function def mergeSort(arr): if len(arr) > 1: #Finding the middle of the array r = len(arr)//2 #Dividing array into two halves leftArray = arr[:r] rightArray = arr[r:] #Calling mergesort function on subparts of array mergeSort(leftArray) mergeSort(rightArray) i = j = k = 0 #Copying data to temp arrays leftArray and rightArray while i < len(leftArray) and j < len(rightArray): if leftArray[i] < rightArray[j]: arr[k] = leftArray[i] i += 1 else: arr[k] = rightArray[j] j += 1 k += 1 while i < len(leftArray): arr[k] = leftArray[i] i += 1 k += 1 while j < len(rightArray): arr[k] = rightArray[j] j += 1 k += 1 #function to print the array def display(arr): for i in range(len(arr)): print(arr[i], end=" ") print() #driver code if __name__ == '__main__': arr = [6, 5, 12, 10, 9, 1] print("Original array") display(arr) mergeSort(arr) print("Sorted array") display(arr)
Original array 6 5 12 10 9 1 Sorted array 1 5 6 9 10 12
- Best-case: In the best-case scenario, we are given the array which is already sorted, so we can use a flag in our code to check if the array is already sorted or not.
- Worst-case: In the worst-case scenario, we will divide the array into two sub-arrays and hence we will perform logn operations and we have to do this for n iterations. So in the worst case, the time complexity will be O(nlogn).
- In every other case, we have to apply the technique of divide and conquer and hence we can conclude the time complexity of merge sort as follows:
Best Time Complexity: O(nlogn)
Average Time Complexity: O(nlogn)
Worst Time Complexity: O(nlogn)
For the application of Merge Sort algorithm n auxiliary space is required as the elements of a given array are copied into new arrays, each containing a single element only. Hence space complexity is O(n).
- Sorting of linked lists is done using merge sorting without taking extra space.
- Merge sorting algorithm is used in external sorting.
- Counting of inversion in a list is done by using merge sort.
- Merge sorting algorithm is used when we have a time constraint of sorting a list. Like sorting in O(nlogn).
Thanks for reading!
If you found this article useful please support us by commenting “nice article” and don’t forget to share it with your friends.