Merge Sort Python Tutorial – An Efficient Way Of Sorting

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= 103), the algorithm will take 2  iterations that is  106

Merge Sort Python
Merge Sort Python

 But suppose you are given a data which is more than 103 , let say 105 then your algorithm will take 1010 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.

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


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



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

Merge Sort Python
Merge Sort Python

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: Compare 2 with 6  and 1 with 4 , and place them in sorted order.

Merge Sort Python
Merge Sort Python

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

Merge Sort Python
Merge Sort Python

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


Step : 1

Step : 2

Step : 3

Step : 4

Merging Subarrays

merge(left, right, Array)

Step : 1

Step : 2

Step : 3

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,

  • 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 Python
Merge Sort Python

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 :

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 Comment