Merge Sort in Python
Merge sort resembles the quick sort algorithm in that it operates on the principle of divide and conquer. It stands out as one of the most widely used and effective sorting algorithms. It serves as an exemplary instance of algorithms that fall under the divide and conquer classification.
It splits the provided list into two segments, recursively processes each half, and subsequently merges the two sorted segments. We will define the merge function that facilitates the merging of the two halves.
The sublists are repeatedly split in half until each contains a single element. Subsequently, we merge the pairs of one-element lists into two-element lists, sorting them concurrently. These sorted two-element pairs are then combined into four-element lists, and this process continues until we obtain the fully sorted list.
Merge Sort Concept
Let's see the following Merge sort diagram.
The provided list has been split into two segments. The unequal division of the list is of no consequence.
Merge sort can be executed through two methods: the top-down approach and the bottom-up approach. In the example provided above, we utilized the top-down approach, which is the most commonly employed method of Merge sort.
The bottom-up method offers greater optimization, which we will clarify later.
The main part of the algorithm is that how we combine 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 observe the first element of both lists. We find the B's first element is smaller, so we add this in our sorted list and move forward in the B list.
- A : [ 2 , 4, 7, 8]
- B : [1, 3 , 11]
- Sorted : 1
Now we look at the next pair of elements 2 and 3. 2 is smaller so we add it into our sorted list and move forward to the list.
- A : [ 2 , 4, 7, 8]
- B : [1, 3 , 11]
- Sorted : 1
By continuing this procedure, we ultimately arrive at the ordered sequence of {1, 2, 3, 4, 7, 8, 11}. There exist two exceptional scenarios.
What occurs when both sublists contain identical elements? In this scenario, we have the option to advance either sublist and incorporate the element into the sorted list. Essentially, we are able to progress through both sublists and append the elements to the sorted list.
One of the sublists is empty. When we deplete the elements in one sublist, we can proceed by appending the elements from the second sublist in succession.
It is important to note that we have the ability to arrange the elements in any desired sequence. While the provided list is sorted in ascending order, it can also be effortlessly organized in descending order.
Implementation of Merge Sort
The merge sort algorithm is executed utilizing a top-down methodology. It may appear somewhat challenging, thus we will clarify each step thoroughly. In this context, we will apply this algorithm to two varieties of collections - a list of integer elements (commonly used for teaching sorting) and a custom object (representing a more practical and realistic use case).
Sorting Array
The fundamental principle of an algorithm involves splitting a (sub)list into two equal parts and sorting them through recursive methods. This process is repeated until we obtain lists that contain a single element. Let’s examine the subsequent function 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 main objective is to segment the list into smaller sections prior to the sorting process. To obtain the integer values, we utilize the // operator for our index calculations.
Let's understand the above procedure by following steps.
- First step is to create copies of lists. The first list contains the lists from [leftindex,...,middle] and the second from [middle+1,?,rightindex] .
- 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.
Python Program for Merge Sort
Let us consider an example to illustrate the merge sort algorithm in Python.
# Here, we are declaring the function to divide the lists in to the two sub lists
# Here, we are passing the list1, left index, right index as the parameters
def merge_sort(list1, left_index, right_index):
if left_index >= right_index: # here, we are checking the if condition
return
middle = (left_index + right_index)//2
# Here, we are finding the middle of the given two numbers
merge_sort(list1, left_index, middle)
# Here, we are calling the merge sort function till the middle number we got
merge_sort(list1, middle + 1, right_index)
# Here, we are calling the merge sort function till the end of the list i.e., right index
merge(list1, left_index, right_index, middle)
# Here, we are calling the merge function to merge the divided list using the merge # sort function above
# Here, we are defining a function for merge the list after dividing
def merge(list1, left_index, right_index, middle):
# Here, we are creating subparts of a lists
left_sublist = list1[left_index:middle + 1]
right_sublist = list1[middle+1:right_index+1]
# Here, we are initializing the 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
# Here, we are traversing the both copies until we get run out one element
while left_sublist_index < len(left_sublist) and right_sublist_index < len(right_sublist): # here, we are declaring a while loop
# 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]:
# Here, we are checking the if condition, if it is true then we will enter the block
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
# Here, we are moving forward in the sorted part
sorted_index = sorted_index + 1
# Here, we will go through the remaining elements and add them
while left_sublist_index < len(left_sublist): # here, we are declaring a while loop
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):# here, we are declaring a while loop
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]
print("The given list before performing the merge sort is: ", list1)
# Here, this is the input unsorted array given by the user
merge_sort(list1, 0, len(list1) -1)
print("The given list after performing the merge sort is:", list1)
# here, we are printing the list1 after performing the merge sort amd the merge
# functions
Output:
The given list before performing the merge sort is:
[44, 65, 2, 3, 58, 14, 57, 23, 10, 1, 7, 74, 48]
The given list after performing the merge sort is:
[1, 2, 3, 7, 10, 14, 23, 44, 48, 57, 58, 65, 74]
Sorting Custom Objects
It is also possible to arrange custom objects through the use of a Python class. This approach is quite akin to the previous one; however, we must enhance its adaptability by allowing the inclusion of a comparison function.
We will develop a personalized class, Car, and incorporate several attributes into it. We will implement some modifications in the following algorithm to enhance its flexibility. This can be achieved through the use of lambda functions.
Python Program For Sorting Custom Objects
Allow us to illustrate the process of sorting custom objects in Python through an example.
class Car: # here, we are declaring a class named car
def __init__(self, make, model, year):
self.make = make
# Here, we are using the self to declare the make variables locally
self.model = model
# Here, we are using the self to declare the model variables locally
self.year = year
# Here, we are using the self to declare the year variables locally
def __str__(self):
return str.format("Make: {}, Model: {}, Year: {}", self.make, self.model, self.year)
# Here, we are returning the format of the strings given
def merge(list1, l, r, m, comp_fun):
# Here, we are defining a function for merge the list using the compound function
left_copy = list1[l:m + 1] # here, we are coping the left part of the list
r_sublist = list1[m+1:r+1] # here, we are coping the right part of the list
left_copy_index = 0 # here, we are coping the left part indexes of the list
r_sublist_index = 0 # here, we are coping the right part indexes of the list
sorted_index = l
while left_copy_index < len(left_copy) and r_sublist_index < len(r_sublist):
# Here, we are declaring a while loop
# Here, we are using the comp_fun instead of a simple comparison operator
if comp_fun(left_copy[left_copy_index], r_sublist[r_sublist_index]):
# Here, we are checking the if condition, if it is true then we will enter the block
list1[sorted_index] = left_copy[left_copy_index]
left_copy_index = left_copy_index + 1
else: # if the condition is false then we will enter the else block
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): # Here, we are declaring a while loop
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): # Here, we are declaring a while loop
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):
# Here, we are declaring the merge sort function to sort the given list
if l >= r:
# Here, we are checking the if condition, if it is true then we will enter the block
return
m = (l + r)//2 # here, we are finding the middle element of the list
merge_sort(list1, l, m, comp_fun)
# Here, we are calling the merge sort function till the middle number we got
merge_sort(list1, m + 1, r, comp_fun)
# Here, we are calling the merge sort function from the middle number we got
merge(list1, l, r, m, comp_fun)
# Here, we are calling the merge function to merge the divided list using the merge # sort function above
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: # here, we are declaring the for loop to iterate through list1
print(car) # here, we are printing all the data of the car and the list
print()
merge_sort(list1, 0, len(list1) -1, lambda carA, carB: carA.make < carB.make)
print("Cars sorted by make:")
for car in list1: # here, we are declaring the for loop to iterate through list1
print(car) # here, we are printing all the data of the car and the list
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
The efficiency of the merge sort algorithm can be enhanced. To begin, it is essential to comprehend the distinction between the top-down and bottom-up merge sort methods. The bottom-up technique sorts elements of neighboring lists in an iterative manner, while the top-down method divides the lists into two halves.
The provided list is [10, 4, 2, 12, 1, 3]. Rather than separating it into individual elements like [10], [4], [2], [12], [1], [3], we can create sublists that might already be in order: [10, 4], [2], [1, 12], [3]. We are now prepared to sort these sublists.
Merge sort tends to be an inefficient algorithm regarding both time complexity and space usage when applied to smaller sublists. Consequently, insertion sort proves to be a more efficient algorithm than merge sort for these smaller sublists.
Conclusion
Merge sort is a widely-used and effective algorithm, particularly well-suited for sorting large datasets. Its performance is not influenced by any adverse choices that could result in poor execution times.
One significant drawback of merge sort is its requirement for extra memory, which is utilized for holding temporary copies of lists prior to the merging process. Nevertheless, merge sort is extensively employed in software applications due to its rapid performance and ability to deliver outstanding results.
We have briefly covered the concept of merge sort and implemented it on a basic list of integers as well as on user-defined objects through a lambda function employed for comparison.