# Merge Sort in Python

Vaibhhav Khetarpal Oct 10, 2023

Merge sort is a popular sorting algorithm utilized to sort the elements of any given data structure. This tutorial discusses the merge sort algorithm and how to implement it in Python.

Merge sort is a prime example of the divide-and-conquer approach and is utilized to sort large data sets. The algorithm begins by dividing the given data structure into two parts and then repeats the same process on both halves. Finally, it combines the halves back together to obtain sorted values efficiently. Hence, we call it a prime example of the `divide-and-conquer` approach.

The best part about this algorithm is that it has a consistent time complexity of `O(nlogn)` in all three possible cases (average case, best case, and worst case). Due to this fact, it is generally considered efficient and is preferred for large data sets.

We will now see how to implement the merge sort algorithm using the Python programming language.

## Use Recursion to Implement Merge Sort in Python

Merge sort is simply implemented in Python with the help of a recursive function.

The following code uses recursion to implement merge sort in Python.

``````def m(left, right):
if not len(left) or not len(right):
return left or right

result = []
i, j = 0, 0
while len(result) < len(left) + len(right):
if left[i] < right[j]:
result.append(left[i])
i += 1
else:
result.append(right[j])
j += 1
if i == len(left) or j == len(right):
result.extend(left[i:] or right[j:])
break

return result

def msort(list):
if len(list) < 2:
return list

middle = int(len(list) / 2)
left = msort(list[:middle])
right = msort(list[middle:])

return m(left, right)

lst = [5, 9, 3, 7, 15, 6]
print("Given List:")
print(lst)
print("\n")
print("Sorted List:")
print(msort(lst))
``````

The above code provides the following output:

``````Given List:
[5, 9, 3, 7, 15, 6]
Sorted List:
[3, 5, 6, 7, 9, 15]
``````

### Code Explanation:

• The given list is separated into two halves, `left` and `right` in every recursive call as long as two adjacent values are not obtained.
• The `m()` function is created and utilized to merge the two halves that are originally divided in the first step.
• The `msort()` function carries out most of the dividing and the sorting part of the given list in the program.

## Use Iterative Merge Sort in Python

The iterative merge sort algorithm is a little different from the general recursive method as the former makes use of the bottom-up approach while the latter uses the top-to-bottom approach. However, the time complexity and the final answer remain exactly the same in both methods.

Moreover, the recursive merge sort method makes use of an explicit auxiliary stack, while there is no need for it in the iterative merge sort algorithm implementation.

The following code uses the iterative merge sort algorithm to implement merge sort in Python.

``````def msort(a):
width = 1
n = len(a)
while width < n:
l = 0
while l < n:
r = min(l + (width * 2 - 1), n - 1)
m = (l + r) // 2
if width > n // 2:
m = r - (n % width)
mer(a, l, m, r)
l += width * 2
width *= 2
return a

def mer(a, l, m, r):
n1 = m - l + 1
n2 = r - m
L =  * n1
R =  * n2
for i in range(0, n1):
L[i] = a[l + i]
for i in range(0, n2):
R[i] = a[m + i + 1]

i, j, k = 0, 0, l
while i < n1 and j < n2:
if L[i] > R[j]:
a[k] = R[j]
j += 1
else:
a[k] = L[i]
i += 1
k += 1

while i < n1:
a[k] = L[i]
i += 1
k += 1

while j < n2:
a[k] = R[j]
j += 1
k += 1

a = [5, 9, 3, 7, 15, 6]
print("Given List:")
print(a)
msort(a)
print("Sorted List:")
print(a)
``````

The above code provides the following output:

``````Given List:
[5, 9, 3, 7, 15, 6]
Sorted List:
[3, 5, 6, 7, 9, 15]
``````