Merge sort program in Python
In this post, you will learn how to write the merge sort program Using the Python programming language.
Merge sort an efficient, general-purpose, and comparison-based sorting algorithm. It is one of the most important sorting algorithms based on the divide and conquer technique. Merge sort is very popular for its efficiency in sorting the data in a small amount of time with worst-case time complexity Ο(n log n). Merge sort first divides the element lists into their two halves. The sub lists are divided again and again into halves until we get only one element each. Then we combine the pairs of one element lists into two element lists, sorting them in the process and, at last, putting them all together.
These are the processes that merge sort follows-
- Divide- It partitions the n elements of the array into two sub arrays.
- Conquer- It sorts the two sub arrays using merge sort.
- Combine- It merges the two sorted sequences to produce the sorted array.
Merge Sort Example
These are the merge sorting techniques. We have the following lists of array elements.
Here, we have taken pairs of array elements and sort them.
Now combine the two pairs and sort them.
Merge the sorted subsequences and again, sort them.
Complexity of Merge Sort
Suppose n is the number of elements in an array.
Best Time Complexity - O(n)
Worst Time Complexity - O(n2)
Average Time Complexity - O(n2)
Advantages Of Merge Sort
- Merge sort is a stable sorting algorithm.
- Merge sort is well suited for large data set.
- It has a consistent running time and carries out different bits at similar times in a stage.
Disadvantages Of Merge Sort
- Slower comparative to the other sort algorithms for smaller tasks.
- At least twice the memory requirements than other sorts.
Merge Sort Program in Python
def merge_sort(arr):
if len(arr) > 1:
a = len(arr)//2
left = arr[:a]
right = arr[a:]
# Sort the two halves
merge_sort(left)
merge_sort(right)
b = c = d = 0
while b < len(left) and c < len(right):
if left[b] < right[c]:
arr[d] = left[b]
b += 1
else:
arr[d] = right[c]
c += 1
d += 1
while b < len(left):
arr[d] = left[b]
b += 1
d += 1
while c < len(right):
arr[d] = right[c]
c += 1
d += 1
def display_list(arr):
for i in range(len(arr)):
print(arr[i], end=" ")
print()
# Driver program
if __name__ == '__main__':
arr = [34,54,11,22,64,76,23,44,86,17]
merge_sort(arr)
print("Sorted array is: ")
display_list(arr)
Output of the above code:
Sorted array is:
11 17 22 23 34 44 54 64 76 86
Related Articles
Convert Python list to numpy arrayConvert string to list Python
Python program to list even and odd numbers of a list
Python loop through list
Sort list in descending order Python
Convert array to list Python
Python take screenshot of specific window
Web scraping Python BeautifulSoup
Check if two strings are anagrams Python
Python program to add two numbers
Print new line python
Python for loop index
Convert List to Dataframe Python
numpy random choice
Dictionary inside list python
Check if list is empty Python
Python raise keyword
Python program to get the largest number from a list
Python program to map two lists into a dictionary