Merge Sort using Python

Merge Sort is a technique that is used for sorting elements in an array using a special method known as divide and conquer. It is the best example of the application of divide and conquers. It is one of the most popular sorting algorithms. In this sorting technique, the array is divided into sub-arrays. Each subarray is then sorted individually. After sorting all the sub-arrays, we will combine them to form a sorted array. It is based on the principle of dividing the array into two halves and then again dividing these two sub-halves. We will repeat these processes until we don’t get an array of size 1. Then we will sort these sub-arrays and combine them. We will combine all the sub-arrays until we don’t get a sorted array of the same size as the initial array.

Merge sort is one of the most efficient sorting techniques to sort the data in a small amount of time. While the other sorting algorithm like selection sort, insertion sort, and bubble sort takes O(n²) time to sort the data in the worst-case scenario, merge sort only takes O(nlogn) time to sort the data.

Divide and Conquer Strategy

With the help of this strategy, we can divide a problem into sub-problems. We solve each sub-problem one by one. Once we have the solution to each sub-problems, then we can combine these sub-problems to form the final solution. This is how we solve the main problem using divide and conquer.

For example, if we have to sort an array. Then a sub-problem would be to sort a sub-array section of the array, starting at index m and ending at index r. This sub-array can be denoted as arr[m..r].

Divide

The middle point of the array between m and r is p. We can divide the array into sub-array with the sizes arr[m..p] and arr[p+1..r].

Conquer

In the step, we will sort both arrays and then combine them to form the solution of the actual array. But if we still haven’t reached the base case, we will divide these sub-arrays and try to sort them.

Combine

When we have solved all the sub-problem, then we will use this step to combine them and get the solution to the main problem. In the case of arrays, once we have sorted all the sub-arrays, then we will combine those sub-arrays to get the final sorted array. When we reach the base case, we get two sorted sub-arrays: arr[m..p] and arr[p+1..q]. We will combine these to get a sorted array as arr[m..q].

Merge Sort Algorithm

In this algorithm, the function divides the array into halves repeatedly until we get to the stage where we can perform the merge sort on a subarray of size 1. The condition for that will be when m==p. After that, the merge function will combine the sorted arrays into a larger array until the whole array is combined or merged.

Merge sort is a recursive algorithm. It means that it repeats the process of dividing the array into sub-arrays until we get a base case. All recursive algorithms are dependent on the base case. It also needs to have the ability to combine those base cases. The merge sort is exactly the same. The most important step in this whole process is the merge step. Because if we don’t do it correctly, we will get an array that might be unsorted or partially sorted. The merge step in the merge sort algorithm is responsible for merging two subarrays or two small arrays which are already sorted. After combining these sorted sub-arrays, we will get another array that will be sorted.

Code for Merge Sort Using python

# MergeSort Algorithm in Python
def merge_Sort(array):
    if len(array) > 1:


        #  x is the mid-point from where the array is divided into two subarrays
        x = len(array)//2
        P = array[:x]
        Q = array[x:]


       # Sorting the two halves of the array
        merge_Sort(P)
        merge_Sort(Q)


        i = j = k = 0
        while i < len(P) and j < len(Q):
            if P[i] < Q[j]:
                array[k] = P[i]
                i += 1
            else:
                array[k] = Q[j]
                j += 1
            k += 1


        while i < len(P):
            array[k] = P[i]
            i += 1
            k += 1


        while j < len(Q):
            array[k] = Q[j]
            j += 1
            k += 1




# Printing the sorted array
def printList(list):
    for i in range(len(list)):
        print(list[i], end=" ")
    print()


if __name__ == '__main__':
    list = [11,90,76,5,34,7,98,66]


    merge_Sort(list)


    print("Sorted array using merge sort is: ")
    printList(list)

Output

Sorted array using merge sort is: 
5 7 11 34 66 76 90 98

Explanation

In the above code, we have used a function merge_Sort to sort the array with random elements. Inside that function, we have used three variables: x, P, and Q. x is the mid-point between the first and last index. P and Q are used to copy the two divided sub-arrays. After that, we recursively solved those sub-arrays. Once we reach the base case, we have used three more variables: i, j, and k. These variables are used to merge the sorted sub-arrays. We will compare the subarrays. The array with a smaller number at the given index will be placed in the index k of the new sorted array. We will increment the value of k after each comparison. And based on which condition gets satisfied, we will increment the value of i and j.  We have used three while loops for each condition. One while loop is used to check if the variable i and j are within the array size limits. Another while loop is used when the length of P is larger than Q. Last while loop is used when the size of Q is larger than P. Lastly, we have printed the value of the sorted array list.

Time Complexity

The best case Complexity of Merge Sort is O(n*logn).

The worst Case Complexity of Merge Sort is O(n*logn).

The average Case Complexity of Merge Sort is O(n*logn).

The space Complexity of Merge Sort is O(n).

Advantages Of Merge Sort

• Merge sort is used to sort data with a large number of elements.
• Merge sort can be used to access the data in a sequential manner. Hence we don’t need the use for random access.
• Merge sort is an example of a stable sorting algorithm.
• Merge sort has the same time complexity for best case, worst case, and average case.

Disadvantages Of Merge Sort

• It requires an array of the same size as the original array to store the final sorted array, which needs extra space. Hence its space complexity is O(n).
• It is not efficient when it comes to sorting data sets with small sizes.

Applications

• Merge sort is used for e-commerce applications.
• Merge sort is used for both internal and external sorting.
• It is used in organizing MP3 libraries.
• It is also used to display Google PageRank results.
• Merge sort is used in various problems like inversion count problems.

Conclusion

Merge sort has a very important role in today’s applications. For a large amount of data set present on the internet, merge sort can easily and efficiently sort the data set. It is used as a basic strategy for all practical applications in day-to-day life. Hence in this lecture, we have mentioned the algorithm along with its advantage and disadvantage.