Merge Sort in Python Programming | Example

Merge Sort in Python Programming | Example


Hello guys and welcome to Python Programming
tutorials by Amuls Academy, and today in this tutorial we are discussing about the merge
sort algorithm, so we will see how to sort the list of numbers using this algorithm. So this
name merge sort tells that, to sort the list of number we need to merge the list but to
merge anything we need divided parts right?, so to sort the list of numbers using this
algorithm first we need to divide the list after that we need to merge that divided list. so this how this merge sort will work, first
we will take a list and we will divide it next we will merge that. ok so now we will see what is Merge sort we
will learn more about this ok. so the first is, this merge sort is divide
and conquer algorithm. So this divide and conquer is an algorithmic
strategy, where what we will do is we will divide our problem into subproblems then we
will find out the solution for that subproblems, then we will combine that result and we will
get the output so we already discussed about the Quicksort which is a divide and conquer
algorithm right?, That algorithm is also based on this strategy. Here merge sort is also based on this divide
and conquer algorithm. So that is nothing but first we will divide
the given list next we will conquer it that is nothing but we will find out the solution
for the sub list next and the last step we will combine the results. So these are the three steps of divide and
conquer strategy, divide conquer and combine. In the first step we will divide the list
to sublist, then we will find out the solution for that sublist and we will combine the results. So here in the merge sort idea is we will
split the unsorted list in to sublist, we will divide the given list to sublist until
the sublist contains single element as we know if a list contains single element that
means that is sorted right?, so we will divide the given list until it contains single element. Next step is merging, so we’ll merge that,
we will sort that and finally we will combine the result. so I’ll take an example so you will get the
clear picture. so now if anyone give you the list of numbers
and ask you to sort them using merge sort algorithm then ok so here i will take list
of numbers i am taking random numbers here and here we can see this is not sorted. so i will take this list name at list1 you
can take any. so i will take the index as, and these are
all the index. so the first step in merge sort algorithm
is, we need to divide the given list, but the question is how to divide that so what
we can do is we can find out the middle element of this list1 and then we can divide the list
based on that middle element, so here to find out the middle element what i am doing is,
i will take the length of list 1 truncated division 2, here we can see length of list1,
1234567 there are 7 elements, so length of list1 will be 7, truncated division 2 we will
get 3, so that is nothing but 3 will be the our middle element ok so now i need to divide
this list based on this index. so i will divide the list like this ok we
got two sublist now but here we can see still in this sublist contains three element or
4 elements i need to divide this until i will get the single element in the list ok so now
again i need to divide this sublist. So for that i will use the same strategy that
is i will find out the middle element and i will divide that. So here index will be 0 1 2 0 1 2 3. So to divide this sublist here length is 3,
3 truncated division 2 so that’s is nothing but 1, so i will get this as the middle element
so i will divide the list like this, here it will contains 20, this will contain 1 and
50.so here what i am doing is i am not including the middle element in the first sublist, this
is the left part right?, in the left part i am not including the middle element. in the right part i am including the middle
element. So here in the left part i am taking the element
from the first index to the last but one index of the middle element ok so here i am taking
till here as the left element. this will be right ok that’s why here i will
get 1 and 50 and here i will get 20 and here i will get it contains 0123 right?, so total
four so this will be the middle element so i will get 40 and 10 here, 5 and 17 here. so i hope now you know how to divide the list.I
need to find out the middle element here 2 is the middle element so i will take the left
sublist as 40 and 10. So in the sublist i will take from the first
element to the middle element, i am not taking the middle element in the left sublist ok
i am including that in this right sublist. so now again here we can see the first sublist
this contains the single element. So no need to further divide it but these
three contains 2 2 elements so i need to divide that. so now if i divide this 1 and 50 i will get
1 and 50. here i will get 40 and 10. here i will get 5 and 17. it contains 01 01 01 index that is nothing
but two elements so if i divided 2 truncated division 2 I’ll get one ok so this will be
the middle element so I’ll take the first element as this and second element as right
sublist. ok so now here we can see we got the sublist
with the single element so now dividing step is over. so we divided the list in such a way that
now our sublist contains single element now we need to merge that ok so next step is merging. So for merging what i need to do is, so first
here I’ll take 1 and 50 because i will start with this step ok so if this is the one step,
this is the second step, this will be the third step right?, so i need to start from
here so i need to merge these two first ok 1 and 50, so i need to compare this one is
less than 50 or not yes right?, so i will write it as 1 and 50 i will merge them. Next i will see 40 and 10, here 40 is greater
than 10 so that’s why i need write 10 and 40. 5 and 17 , 5 is less than 17 ok so i can write
it as 5 and 17. So i need to check the element which is present
in the left sublist is less than right sublist element. so next i need to take this 20 now and this
now so we are done with the combining this step 3 so i need to move to the next step
now step 2 ok so here we can see 20 and 1 and 50 so i need to first check whether 20
is less than 1 no it is not so remember that here i am sorting the number in the ascending
order so first i want smaller number right?, so i need to check the value present in the
left side this will be the left side and this will be the right side ok so whether 20 is
less than 1 NO so i need to write one here ok next again i will check whether 20 is less
than 50 yes so i need to write 20 here. So now remaining element is 50 i need to write
here so now i will move on to this side and here we have this two sublist so for that
we will get 4 elements we know that because here 2 2 total 4 elements. So now i need to check whether 10 is less
than 5, No so i need to write five here again i will check whether 10 is less than 17 yes
so i can write 10 here now again i will check whether 40 is less than 17 no right?, 40 is
not less than 17 so i will write 17 here 40 here. Now lastly i need to combine this two sublist
ok so i will write it here, so i will write down that ok so 1 20 and 50, 5 10 17 and 40. so now i need to combine them merge them right?,
so first i will check whether one ok is less than 5 yes so i will write 1 here. now 1 is done right?, so i will move to the
next value, whether 20 is less than 5?, No 5 is the smaller value so i need to write
5 here so now i need to check with this value, whether 20 is less than 10 No so i need to
write 10 here i need to move to the 17, ok i will check whether 20 is less than 17 no
so i will write 17 here and i will check for the 40, whether 20 is less than 40 yes so
i need to write 20 here and i need to move to the next value here that is 50. Whether 50 is less than 40 No so i need to
write 40 here, the remaining value is 50 so i need to write it here ok so in this way
you need to compare the values right?, here also you need to compare like that. So in this way we can sort the numbers using
merge sort algorithm. so this is in the ascending order, if you
want in the descending order then you just need to find out the maximum value here. so in the next tutorial we will see the algorithm
as well as we will write the program for that. so that’s it for now guys, thank you for watching
don’t forget to subscribe to my channel i will meet you in next class till then take
care.

7 thoughts on “Merge Sort in Python Programming | Example

  1. Hi Mam, Can you plz help me with the output and explanation of the following programming question?

    list1=[1,4,3,2,5,6]

    for item in list1:

    print("item= ",item)

    if item>2:

    list1.remove(item)

Leave a Reply

Your email address will not be published. Required fields are marked *