Python Program for Merge Sort

Language Used: Python

Merge Sort:

Merge Sort is a Divide and Conquer algorithm. It divides input array in two halves, calls itself for the two halves and then merges the two sorted halves. The merge() function is used for merging two halves.

How it works?

First divide the list into the smallest unit, then compare each element with the adjacent list to sort and merge the two adjacent lists. Finally all the elements are sorted and merged.

Source Code:

Output:

Splitting  [54, 26, 93, 17, 77, 31, 44, 55, 20]
Splitting  [54, 26, 93, 17]
Splitting  [54, 26]
Splitting  [54]
Merging  [54]
Splitting  [26]
Merging  [26]
Merging  [26, 54]
Splitting  [93, 17]
Splitting  [93]
Merging  [93]
Splitting  [17]
Merging  [17]
Merging  [17, 93]
Merging  [17, 26, 54, 93]
Splitting  [77, 31, 44, 55, 20]
Splitting  [77, 31]
Splitting  [77]
Merging  [77]
Splitting  [31]
Merging  [31]
Merging  [31, 77]
Splitting  [44, 55, 20]
Splitting  [44]
Merging  [44]
Splitting  [55, 20]
Splitting  [55]
Merging  [55]
Splitting  [20]
Merging  [20]
Merging  [20, 55]
Merging  [20, 44, 55]
Merging  [20, 31, 44, 55, 77]
Merging  [17, 20, 26, 31, 44, 54, 55, 77, 93]
[17, 20, 26, 31, 44, 54, 55, 77, 93]

Description:

Let’s break the code and understand it.

First is the if the statement where if the condition gets satisfied, the following statements are executed.

Calculate the mid value using the formula and initialize the values of lefthalf and righthalf and sort it using the function msort.

Initialize the values of i, j, k as 0.

Now using while loop, iterate the following if_else statements if the condition is satisfied.

Here, len function is used to check the length of the lefthalf and righthalf. The resultant sorted elements are stored and displayed to the user.

For any Educational Assistance,

Refer: https://www.guvi.in/