Understanding Merge Sorting Algorithm With Example And Explanation

Merge Sorting Algorithm - 

This is the one of fastest sorting algorithm. This sorting algorithm based on divide and conquer method where we divide the array in sub-arrays and after that compare them with each other and merge in a single array list.

This algorithm is very much similar with quick sort but the main difference is quick sort consider a pivot element and on the basis of 

pivot process divide and conquer. Same as quick sort small elements are placed at left side and greater elements are placed at right side of the list. 

Merge sort is advisable for large amount of data elements. 


Complexity is the big difference with quick sort, merge sort worst-case complexity is O(n log n), so that merge sort is better than quick sort.


Let's understand first how quick sort works...


Assume we have list of 10 elements,

20, 40, 80, 10, 58, 23, 30, 12


Step - 1

Divide list into sub lists until each list should have single element.

    
note : single element is sorted in itself because there is no other element to be compared.

    A. First get middle of the list.
      
        assuming list has 8 elements so that       
        lower index is 0 and  higher is 7.  

       20 40 80 10 58 23 30 12   


       calculate mid, mid = (lower + higher)/2 , 

       (0+7)/2 = 3 (consider only floor value)

    B. Divide array list into two small lists, 


       0 to mid        =  20, 40, 80, 10   left list


       mid+1 to higher =  58, 23, 30, 12   right list


       20 40 80 10 (Left)         58 23 30 12 (right) 

     

    C. Let's divide left side list first until each  
        list would have single element.

       20, 40, 80, 10


       calculate mid,  mid = (0+3)/2 = 1


       0 to mid        =  20,40   left list


       mid+1 to higher =  80,10   right list


       20 40 (left)         80 10 (right) 

            

    D. Again divide lists until each list would  
        have single element.

       Lets take left side first - 20, 40
       
       calculate mid,  mid = (0+1)/2 = 0

       0 to mid        =  20      left list


       mid+1 to higher =  80      right list

           
       20 (left)          40 (right)

 Let's understand full division by using diagram ...


Merge Sorting Algorithm
Merge Sorting Algorithm. ByTechAchievers.com

Step - 2


Next step is to compare each list with each other and form a new list. Right now we have sub lists which are sorted in itself.

 
    
Rules To Be Followed : - 

1- Rule -  

we will read all the elements till i < left_list_size &&  j <  right_list_size

2 - Rule -  

i will read left side list and j will read right side list.

3 - Rule -  

Compare elements, every small element will be inserted into new list. 
                 
4 - Rule -  
If small element is coming from left side list then i will be incremented by 1 same as with j, If small element is coming from right side then j will be incremented by 1.
   
5 - Rule -  
Do comparing until i , j and pivot index are equal at this condition we will get sorted pivot index.

    

Left Side List
Right Side List
20  40  80 10 

First take 20 and 40 lists

i loop to read first list and j loop to read 2nd loop.

i =0 , j =0
if (list [i] < list [j] ), 20 < 40

Small element is from left list i.e i would be incremented by 1.
New list would be 20

i =1 , j =0 loop ends,i exceeds the limit. 
j element will be inserted at the end into the new list.

New list- 20,40
------------------------------------------

Next process with 20,40  and 80
i loop to read first list and j loop to read 2nd loop.

i =0 , j =0
if (list [i] < list [j] ), 20 < 80 

Small element is from left list i.e i would be incremented by 1.
New list would be 20

i =1 , j =0
if (list [i] < list [j] ), 40 80 

Small element is from left list i.e i would be incremented by 1.
New list would be 20,40

i =2 , j =0 , loop ends, i exceeds the limit

j element will be inserted at the end into the new list.

New list- 20,40,80
---------------------------------------------


Next process with 20,40,80 and 10
i loop to read first list and j loop to read 2nd loop.

i =0 , j =0
if (list [i] < list [j] ), 20 < 10

Small element is from right list i.e j would be incremented by 1.


New list- 10


i =1 , j =1, loop ends, j exceeds the limit.

i elements will be inserted at the end into the new list.

New list- 10,20,40,80

First take 58 and 23 lists.

i loop to read first list and j loop to read 2nd loop.

i =0 , j =0
if (list [i] < list [j] ), 58 < 23 

Small element is from right list i.e j would be incremented by 1.
New list would be 23

i =0 , j =1 loop ends, j exceeds the limit.
i element will be inserted at the end into the new list.

New list- 23,58

---------------------------------------------

Next process with 23,58 and 30
i loop to read first list and j loop to read 2nd loop.

i =0 , j =0
if (list [i] < list [j] ), 23 < 30 

Small element is from left list i.e i would be incremented by 1.
New list would be 23

i =1 , j =0
if (list [i] < list [j] ), 58 < 30 

Small element is from right list i.e j would be incremented by 1.
New list would be 23,30

i =1 , j =1, loop ends j exceeds the limit

i element will be inserted at the end into the new list.

New list- 23,30,58

---------------------------------------------


Next process with 23,30,58 and 12
i loop to read first list and j loop to read 2nd loop.

i =0 , j =0
if (list [i] < list [j] ), 23 < 12

Small element is from right list i.e j would be incremented by 1.

New list- 12

i =1 , j =1, loop ends, j exceeds the limit.

i elements will be inserted at the end into the new list.

New list- 12,23,30,58
    
Next process with 10,20,40,80 and 12,23,30,58 

i loop to read left list and j loop to read right list. 



i =0 , j =0
if (list [i] < list [j] ), 10 12 

Small element will be inserted into new list


New list is - 10


Small element is from left list i.e i would be incremented by 1.


i =1 , j =0
if (list [i] < list [j] ), 20 12 

Small element will be inserted into new list


New list is - 10,12


Small element is from right list i.e j would be incremented by 1.


i =1 , j =1

if (list [i] < list [j] ), 20 23 


Small element will be inserted into new list


New list is - 10,12,20


Small element is from left list i.e i would be incremented by 1.


i =2 , j =1


if (list [i] < list [j] ), 40 23 


Small element will be inserted into new list


New list is - 10,12,20,23


Small element is from right list i.e j would be incremented by 1.


i =2 , j =2


if (list [i] < list [j] ), 40 30


Small element will be inserted into new list


New list is - 10,12,20,23,30


Small element is from right list i.e j would be incremented by 1.


i =2 , j =3

if (list [i] < list [j] ), 40 58


Small element will be inserted into new list


New list is - 10,12,20,23,30,40


Small element is from left list i.e i would be incremented by 1.


i =3 , j =3

if (list [i] < list [j] ), 80 58 


Small element will be inserted into new list


New list is - 10,12,20,23,30,40,58


Small element is from right list i.e j would be incremented by 1.


loop ends, j exceeds the limit.


Congrats! Your list is sorted - 10,12,20,23,30,40,58



No comments

Powered by Blogger.