Learn Python – Merge Sort in Python- Basic and advance

Merge kind is comparable to the rapid sort algorithm as works on the concept of divide and conquer. It is one of the most popular and efficient sorting algorithm. It is the high-quality instance for divide and overcome category of algorithms.

It divides the given list in the two halves, calls itself for the two halves and then merges the two sorted halves. We define the merge() feature used to merging two halves.

The sub lists are divided once more and once more into halves until we get the only one element each. Then we mix the pair of one component lists into two issue lists, sorting them in the process. The sorted two element pairs is merged into the 4 component lists, and so on until we get the sorted list.

Merge Sort Concept

Let’s see the following Merge sort diagram.

We have divided the given listing in the two halves. The listing could not be divided in equal components it would not be counted at all.

Merge type can be enforce using the two approaches – top-down approach and bottom-up approach. We use the pinnacle down approach in the above example, which is Merge type most frequently used.

The bottom-up strategy gives the more optimization which we will outline later.

The main section of the algorithm is that how we mix the two sorted sublists. Let’s merge the two sorted merge list.

A : [2, 4, 7, 8]

B : [1, 3, 11]

sorted : empty

First, we look at the first thing of each lists. We find the B’s first aspect is smaller, so we add this in our sorted listing and cross ahead in the B list.

A : [2, 4, 7, 8]

B : [1, 3, 11]

Sorted : 1

Now we look at the next pair of factors 2 and 3 two is smaller so we add it into our sorted listing and go ahead to the list.

A : [2, 4, 7, 8]

B : [1, 3, 11]

Sorted : 1

Continue this procedure and we end up with the sorted listing of {1, 2, 3, 4, 7, 8, 11}. There can be two one of a kind cases.

What if both sublists have same elements – In such case, we can move either one sublist and add the element to the sorted list. Technically, we can move forward in both sublist and add the elements to the sorted list.

We have no element left in one sublist. When we run out the in a sublist simply add the element of the second one after the other.

We need to understand that we can kind the issue in the any order. We type the given list in ascending order but we can easily type in descending order.

Implementation

The merge type algorithm is carried out through suing the top-down approach. It can be appear barely difficult, so we will problematic every step in details. Here, we will put in force this algorithm on two types of collections – integer element’s listing (typically used to introduce sorting) and a customized objects (a greater sensible and sensible scenario).

Sorting Array

The most important concept of algorithm is to divide (sub)list into halves and sort them recursively. We continue the manner till we stop up lists that have solely one element. Let’s apprehend the following feature for division –

def merge_sort(array, left_index, right_index):   
       if left_index >= right_index:   
                 return middle = (left_index + right_index)//2   
       merge_sort(array, left_index, middle)   
       merge_sort(array, middle + 1, right_index)   
       merge(array, left_index, right_index, middle)   

Our predominant center of attention to divide the list into subparts earlier than the sorting happen. We need to get the integer cost so we use the // operator for our indices.

Let’s apprehend the above process by way of following steps.

First step is to create copies of lists. The first list contains the lists from [left_index,…,middle] and the second from [middle+1,?,right_index].

We traverse both copies of list by using the pointer, select the smaller value of the two values and add them to the sorted list. Once we add the element to the list and we move forward in the sorted list regardless.

Add the remaining elements in the other copy to the sorted array.

Let’s implement the merge sort in Python program.

Python Program

# funtion to divide the lists in the two sublists  
def merge_sort(list1, left_index, right_index):  
    if left_index >= right_index:  
        return  
  
    middle = (left_index + right_index)//2  
    merge_sort(list1, left_index, middle)  
    merge_sort(list1, middle + 1, right_index)  
    merge(list1, left_index, right_index, middle)  
  
  
    # Defining a function for merge the list  
def merge(list1, left_index, right_index, middle):  
  
  
   # Creating subparts of a lists  
    left_sublist = list1[left_index:middle + 1]  
    right_sublist = list1[middle+1:right_index+1]  
  
    # Initial values for variables that we use to keep  
    # track of where we are in each list1  
    left_sublist_index = 0  
    right_sublist_index = 0  
    sorted_index = left_index  
  
    # traverse both copies until we get run out one element  
    while left_sublist_index < len(left_sublist) and right_sublist_index < len(right_sublist):  
  
        # If our left_sublist has the smaller element, put it in the sorted  
        # part and then move forward in left_sublist (by increasing the pointer)  
        if left_sublist[left_sublist_index] <= right_sublist[right_sublist_index]:  
            list1[sorted_index] = left_sublist[left_sublist_index]  
            left_sublist_index = left_sublist_index + 1  
        # Otherwise add it into the right sublist  
        else:  
            list1[sorted_index] = right_sublist[right_sublist_index]  
            right_sublist_index = right_sublist_index + 1  
  
  
        # move forward in the sorted part  
        sorted_index = sorted_index + 1  
  
       
    # we will go through the remaining elements and add them  
    while left_sublist_index < len(left_sublist):  
        list1[sorted_index] = left_sublist[left_sublist_index]  
        left_sublist_index = left_sublist_index + 1  
        sorted_index = sorted_index + 1  
  
    while right_sublist_index < len(right_sublist):  
        list1[sorted_index] = right_sublist[right_sublist_index]  
        right_sublist_index = right_sublist_index + 1  
        sorted_index = sorted_index + 1  
  
list1 = [44, 65, 2, 3, 58, 14, 57, 23, 10, 1, 7, 74, 48]  
merge_sort(list1, 0, len(list1) -1)  
print(list1)  

Output:

[1, 2, 3, 7, 10, 14, 23, 44, 48, 57, 58, 65, 74]

Sorting Custom Objects

We can additionally type the custom objects via using the Python class. This algorithm is almost similar to the above but we want to make it greater versatile and pass the contrast function.

We will create a customized class, Car and add a few fields to it. We make few changes in the under algorithm to make it more versatile. We can do this by means of the usage of the lambda functions.

Let’s understand the following example.

Python Program

class Car:  
    def __init__(self, make, model, year):  
        self.make = make  
        self.model = model  
        self.year = year  
  
    def __str__(self):  
        return str.format("Make: {}, Model: {}, Year: {}", self.make, self.model, self.year)  
  
def merge(list1, l, r, m, comp_fun):  
    left_copy = list1[l:m + 1]  
    r_sublist = list1[m+1:r+1]  
  
    left_copy_index = 0  
    r_sublist_index = 0  
    sorted_index = l  
  
    while left_copy_index < len(left_copy) and r_sublist_index < len(r_sublist):  
  
        # We use the comp_fun instead of a simple comparison operator  
        if comp_fun(left_copy[left_copy_index], r_sublist[r_sublist_index]):  
            list1[sorted_index] = left_copy[left_copy_index]  
            left_copy_index = left_copy_index + 1  
        else:  
            list1[sorted_index] = r_sublist[r_sublist_index]  
            r_sublist_index = r_sublist_index + 1  
  
        sorted_index = sorted_index + 1  
  
    while left_copy_index < len(left_copy):  
        list1[sorted_index] = left_copy[left_copy_index]  
        left_copy_index = left_copy_index + 1  
        sorted_index = sorted_index + 1  
  
    while r_sublist_index < len(r_sublist):  
        list1[sorted_index] = r_sublist[r_sublist_index]  
        r_sublist_index = r_sublist_index + 1  
        sorted_index = sorted_index + 1  
  
  
def merge_sort(list1, l, r, comp_fun):  
    if l >= r:  
        return  
  
    m = (l + r)//2  
    merge_sort(list1, l, m, comp_fun)  
    merge_sort(list1, m + 1, r, comp_fun)  
    merge(list1, l, r, m, comp_fun)  
  
car1 = Car("Renault", "33 Duster", 2001)  
car2 = Car("Maruti", "Maruti Suzuki Dzire", 2015)  
car3 = Car("Tata motor", "Jaguar", 2004)  
car4 = Car("Cadillac", "Seville Sedan", 1995)  
  
list1 = [car1, car2, car3, car4]  
  
merge_sort(list1, 0, len(list1) -1, lambda carA, carB: carA.year < carB.year)  
  
print("Cars sorted by year:")  
for car in list1:  
    print(car)  
  
print()  
merge_sort(list1, 0, len(list1) -1, lambda carA, carB: carA.make < carB.make)  
print("Cars sorted by make:")  
for car in list1:  
    print(car)  

Output:

Cars sorted by year:
Make: Cadillac, Model: Seville Sedan, Year: 1995
Make: Renault, Model: 33 Duster, Year: 2001
Make: Tata motor, Model: Jaguar, Year: 2004
Make: Maruti, Model: Maruti Suzuki Dzire, Year: 2015

Cars sorted by make:
Make: Cadillac, Model: Seville Sedan, Year: 1995
Make: Maruti, Model: Maruti Suzuki Dzire, Year: 2015
Make: Renualt, Model: 33 Duster, Year: 2001
Make: Tata motor, Model: Jaguar, Year: 2004

Optimization

We can improve the performance of the merge sort algorithm. First let’s understand the distinction between the top-down and bottom-up merge sort. The bottom-up strategy sorts the elements of adjoining lists iteratively where the top-down approach breaks down the lists into the two halves.

The given list is [10, 4, 2, 12, 1, 3], rather of breaking it down into [10], [4], [2], [12], [1], [3] – we divides into the sublists which may additionally already sorted: [10, 4], [2], [1, 12], [3] and now are prepared to type them.

Merge kind is inefficient algorithm in both time and area for the smaller sublists. So insertion sort is extra environment friendly algorithm than the merge kind for the smaller sublists.

Conclusion

Merge type is popular and efficient algorithm. It is more efficient algorithm for the giant lists. It doesn’t depend on the any unfortunate decisions that lead to horrific runtimes.

There is one most important demerit in the merge sort. It uses the additional reminiscence that is used to save the transient copies of lists earlier than merging them. However Merge kind is broadly used in the software. Its performance is fast and produces the first-rate result.

We have discussed the merge sort thought in quick and put in force it each on easy integer list and on customized objects by a lambda function used for comparison.