In computer science, merge sort is an efficient, general-purpose, and comparison-based sorting algorithm. Most implementations produce a stable sort, which means that the order of equal elements is the same in the input and output.

- Based on Divide and conquer strategy
- Requires extra space to hold the two halves

```
MergeSort(arr[], l, r)
If r > l
Find the middle point to divide the array into two halves: middle m = l+ (r-l)/2
Call mergeSort for first half: Call mergeSort(arr, l, m)
Call mergeSort for second half: Call mergeSort(arr, m+1, r)
Merge the two halves sorted in step 2 and 3: Call merge(arr, l, m, r)
```

```
def mergeSort(arr):
if len(arr) >1:
mid = len(arr)//2 # Finding the mid of the array
L = arr[:mid] # Dividing the array elements
R = arr[mid:] # into 2 halves
mergeSort(L) # Sorting the first half
mergeSort(R) # Sorting the second half
i = j = k = 0
# Copy data to temp arrays L[] and R[]
while i < len(L) and j < len(R):
if L[i] < R[j]:
arr[k] = L[i]
i+= 1
else:
arr[k] = R[j]
j+= 1
k+= 1
# Checking if any element was left
while i < len(L):
arr[k] = L[i]
i+= 1
k+= 1
while j < len(R):
arr[k] = R[j]
j+= 1
k+= 1
# Code to print the list
def printList(arr):
for i in range(len(arr)):
print(arr[i], end =" ")
print()
# driver code to test the above code
if __name__ == '__main__':
arr = [12, 11, 13, 5, 6, 7]
print ("Given array is", end ="\n")
printList(arr)
mergeSort(arr)
print("Sorted array is: ", end ="\n")
printList(arr)
```

All programs will print sorted array as output.

I hope you like this article, to learn more about articles like this you can click here. Thank you for reading.

Thank You!

python
python basic programs
python coding
python interview questions
python programming
python tutor
python

In this lesson on python coding, we will talk about one of the fundamen...

In this lesson on python coding, we will talk about one of the fundamental ...

Follow us on facebook Click Here

Scan from mobile

Scan from mobile