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.

Thank you

So Divide & Conquer problems can be solved conveniently by recursion.

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)

Hi mam,

Please make videos on collections module and regular expressions if possible

Pls make video on binary search

I think He is a kid , but very talented.

Please make video on heap sort