Merge Sort Algorithm Using Python

In this article, we are going to learn about a merge sort algorithm. Merge sort is a popular divide-and-conquer sorting method. Merge sort is widely used because of its speed in sorting data. It’s one of the better illustrations of how to divide and conquer algorithms that may be used in practice. Merge sort separates a list of data into two halves and then, calls these subparts to divide it further into two halves. It repeats the operation until each list component has just one element. By sorting these subparts of one element into two components, it will later merge them together. After sorting, the two-element subpart will be linked with the other two components. This procedure is repeated until the final sorted list of elements is obtained by invoking the function repeatedly.

The basic illustration of the merge sort is given in the following example:

Python Code: The following Python code is for the merge sort algorithm:

def merge_sort(unsortedList):
if len(unsortedList) > 1:
mid = len(unsortedList) // 2
leftList = unsortedList[:mid]
rightList = unsortedList[mid:]

# Recursive call when we go two list (left and right) for sorting
merge_sort(leftList)
merge_sort(rightList)

# Because we have two lists, so we need to iterators for iteration of each list
m = 0
n = 0
# We need one common iterator which iterates to the main list
z = 0

while m < len(leftList) and n < len(rightList):
if leftList[m] <= rightList[n]:
# Here we are using the first left side elements
unsortedList[z] = leftList[m]
# Increment the main iterator
m += 1
else:
unsortedList[z] = rightList[n]
n += 1
z += 1

# If values are left in the list, then we process here
while m < len(leftList):
unsortedList[z] = leftList[m]
m += 1
z += 1

while n < len(rightList):
unsortedList[z]=rightList[n]
n += 1
z += 1

unsortedList = [23,56,0,23,85,100,200,12,32,78,90,102]
merge_sort(unsortedList)
print(unsortedList)

Output:

[0, 12, 23, 23, 32, 56, 78, 85, 90, 100, 102, 200]

This is the recursive way to merge sort implementation. Here are the following steps to obtain the sorted array using this method:

Line 1: We define a function (merge_sort) when we need to sort a list of unsorted elements. Now, we are going to explain all lines of this merge_sort function.
Line 2–5: The first thing we are checking is whether the unsorted list elements have more than 1 element or not. If there is only a single element, there is no need to sort. So, we are checking this first condition.
If the elements are more than 1, then we are trying to get the median value of the list to divide the whole list into two parts (left and right) for further recursive call. Each recursive call divides the list into left and right until two adjacent entries are acquired.
Line 8–9: We call the merge sort recursively for each sublist (left and right).
Line 11–15: The sorting procedure now starts. Each calls two parts that are traversed by the m and n iterators. The z iterator iterates across all of the lists, making modifications as it goes.
Line 17–26: leftList[m] is allocated to the unsortedList[z] slot, and m are incremented if the value at m is less than the value at n. If not, rightList[n] is selected. All values assigned to z are all sorted.
Line 29–37: At the end of this loop, one of the parts may not have been crossed completely. Its contents are assigned to the remaining positions on the list.

Time Complexity:

The time complexity of the merge sort depends upon two factors:

The list split factor which takes log(n)
The second factor merge the two list, which takes linear time, so its complexity is O(n)

Thus, the total complexity is based on the previous two factors of the merge sort is O(n.logn).

Advantages of the Merge Sort Algorithm:

Merge sorting makes it simple to sort big data sets.
Merge sort may access data in order, thus random access isn’t required.
Merge sort is a reliable sorting method.

Disadvantages of the Merge Sort Algorithm:

The merge sort requires a similar size array to sort the list, which is a disadvantage of the memory use.
When sorting smaller data sets, it takes longer.

Conclusion:

Merge sorting is a fast and versatile sorting method. Its key benefit is the algorithm’s consistent runtime and efficiency while sorting big arrays. Compared to Quick Sort, it does not rely on any faulty judgments that result in long runtimes. The merge sort is the best algorithm to sort the elements. However, the main drawback of the merge sort is that it uses a lot of memory before merging the elements. It’s also very useful for future software engineering, where they can build more sorting algorithms based on the divide-and-conquer method.

We saw the standard example of the merge sort without coding first to understand how this analogy works, and then we implemented similar steps in Python programming. Now, we are aware of the divide and conquer technology of the merge sort. We hope you found this article helpful. Check out Linux Hint for more tips and information.