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. 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.

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