Welcome to Merge Sort Python Tutorial. In this tutorial, you will learn a very important topic of data structure that is Merge sort. Here i will cover these topics – merge sort introduction, algorithm, implementation, complexity, applications and some other concept. So let’s start merge sort in python.

We have many sorting techniques like Insertion sort, Bubble sort, selection sort. But these techniques are poor. It means, for example, for a given n which is equal to 1000 **(n=1000= 10^{3}),** the algorithm will take

**n**

^{2 }iterations that is

*10*^{6}* ^{ }*But suppose you are given a data which is more than

**, let say**

*10*^{3}**then your algorithm will take**

*10*^{5}**iterations. These algorithms will take lots of time to execute, so now time to discuss something well. So i am going to discuss a very important sorting algorithm which is also often used algorithm, which is called merge algorithm. So let’s start Merge Sort Python Tutorial.**

*10*^{10}## Merge Sort Python Tutorial – A Very Fast Sorting Method

### What is Merge Sort ?

- Merge sort based on
**Divide and Conquer**approach. - That means it divides the array into two parts, those sub-arrays will be divided into other two equal parts. We will divide the array in this manner until we get single element in each part because single element is already sorted. After completion of dividing array, its time to conquer or merge them together but in sorted manner. Hence we get a sorted array.
- Merge sort is recursive(method that call itself).
- Very efficient for large data set.

### How Merge Sort Works ?

In this section you will learn, how merge sort works.

**Conceptually, Merge sort works in following manner.**

- Divide an unsorted array into two subarrays, and repeat dividing subarrays into further subarrays until you get single element in each part or sub-array.
- Merge these subarrays in the same way as had divided it, but in sorted manner. This process will repeated until there is only 1 subarray remaining. This will be your sorted array.

**Let’s understand it with an example –**

Let’s consider we have an array** [2,6,1,4]**

2 |
6 |
1 |
4 |

**Dividing
**

**Step 1 :** Now we will divide this array into two subarrays

**
Step 2:** Now we will divide these subarrays into further subarrays

Now we have only one element in each subarray, so it’s time to merge them. We have to merge them in the same manner as had divided it, but in sorted manner.

**Step 3: C**ompare 2 with 6 and 1 with 4 , and place them in sorted order.

**Step 3:** Now we have to compare the above two sorted subarrays and sort them.

This is our sorted array. In this way you can sort a large data using merge sort method.

### Merge Sort Algorithm

Now we will see merge sort algorithm. Merge sort takes place in two parts – first one is dividing array into subarrays and then merging them in sorted order. So we will see it one by one.

#### Dividing array into subarrays

**Mergesort(Array)**

**Step : 1**

1 2 3 |
set n = length(Array) If (n<2) then return |

**Step : 2**

1 2 3 4 5 |
set mid = n/2 Initialize array “left” having size (mid) Initialize array “right” having size (n-mid) |

**Step : 3**

1 2 3 4 5 6 7 8 9 10 11 |
for i = 0 to mid – 1 left [i] = Array[i] [exit loop] for i = mid to n-1 right[i] = Array[i] [exit loop] |

**Step : 4**

1 2 3 4 5 |
call mergesort(left) Call mergesort(right) Call merge(left,right,Array) |

**Merging Subarrays**

**merge(left, right, Array)**

**Step : 1**

1 2 3 |
set i = 0, j =0, k = 0 [i,j,k will represent the indexes of left,right and Array respectively. ] |

**Step : 2**

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 |
while (i<length(left) and j<length(right) { If (left[i] < right[j]) Then set Array[k] = left[i] Increase i by 1 [end of if statement] else Set Array[k] = right[j] Increase j by 1 [end of else statement] Increase k by 1 [end of while loop] |

**Step : 3**

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 |
while (i < length(left)) { Set Array[k] = left[i] i = i + 1 k = k + 1 } While (j < length(right)) { Array[k] = Right[j] Increase j by 1 Increase k by 1 } |

### Merge Sort Python Example

Now we will see, how to implement merge sort in python practically.

The code of merge sort have two parts. So let’s start,

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 |
# Define definition for merge which basically takes two arrays i.e., the left and right part def merge(left, right): result = [] # final result array, that is an empty array #create two indices and initialize with 0 i,j = 0,0 # Till this condition is true, keep on appending elements into resultant array while i<len(left) and j<len(right): if left[i] <= right[j]: result.append(left[i]) #append ith element of left into resultant array i+=1 else: result.append(right[j]) #append jth element of right into resultant array j+=1 # it is basically specifies that if any element is remaining in the left array from - # ith to the last index so that it should appended into the resultant array. And similar - # to the right array. result += left[i:] result += right[j:] return result # Definition for merge sort # this takes an input list def mergesort(lst): if(len(lst)<= 1): # this means that the list is already sorted. return lst mid = int(len(lst)/2) # left array will be mergesort applied over the list from starting index # till the mid index left = mergesort(lst[:mid]) # right array will be mergesort applied recursively over the list from mid index # till the last index right = mergesort(lst[mid:]) return merge(left,right) # finally return merge over left and right # create an array, assign elements into it arr = [1,9,4,3,2] print(mergesort(arr)) # print sorted array |

**merge(left, right)**basically merges two arrays that is left array and right array and gives us the resultant array, which is basically sorted.

**So the result of merge sort is following –**

### Merge Sort – Big Oh Analysis

- Merge sort does
**log n**merge steps because each merge step double the list size. - It does
**n**work for each merge step because it must look at every item. - So it runs on
**O(n log n).**

### Merits Of Merge Sort

- Merge sort can be applied to any file size.
- Merge Sort is useful for sorting linked lists.
- It is always fast even in worst case, its runtime is O(n log n).
- It is stable sort which means that the same element in an array maintain their original positions with respect to each other.

### Demerits Of Merge Sort

- It requires additional memory to sort the elements.
- Recursive calls result in additional overhead making it unsuitable for small number of elements.

### Recommended articles :

- Python Sort Dictionary By Value – Sort With Lambda Function And Operator Module
- Selection Sort Python – A Quick Tutorial and Implementation Guide
- Python Split String By Character – Split String Using split() method
- Linear Search Python – Learn Linear Search With Example
- Best Python Frameworks To Learn In 2018

So that’s it for Merge Sort Python tutorial. If you found this post helpful then please SHARE it with your friends. And for any question you can leave your comments below. Thank You 🙂

## Leave a Reply