Class 9 Summary: Nov 25 : Merge Sort

Blogged By: Jibrael Jos

Merge Sort works on the principle that we can Merge two sorted arrays by looping thru it once

But then even if we could merge two sorted arrays, how does this strategy help in sorting unsorted array ?

Lets take an array
7,23,12,8,6,9,2,76,13,19 and call mergeSort(arr,0,9)

Lets divide array into two half and sort each side somehow like this
Step 1: Divide : 23,7,12,8,6 9,2,76,13,19
Step 2: Sort : 6,7,8,12,23 and 2,9,13,19,76
Step 3: Now Simple Merge them using a merge function and get
2,6,7,8,9,12,13,19,23,76

But wait a sec ? How did Step 2 happen what method did we use to Sort?
Well !!
Lets divide array into two half and sort each side somehow like this
Step 1: Divide : 23,7 12,8,6
Step 2: Sort : 7,23 and 6,8,12
Step 3: Merge to get 6,7,8,12,23

Big Deal ..... how did you do second step here ?
Lets divide array (23,7) into two half and sort each side somehow like this
Step 1: Divide : 23 7
Step 2: Sort : Now 23 is sorted in itself (since only 1 number)
Step 3:Merge to get 7,23

This is the beauty of a recursive algo like towerOfHanoi .... the logic is simply stated as

MergeSort(lowerBound,upperBound)
MergeSort(lowerBound,middle)
MergeSort(middle+1,upperBound)
Merge(lowerBound,middle+1,upperBound)


But don't forget every recursion should stop somewhere so add a condition in the beginning
if(lowerBound==upperBound)
return;
So how many times does recursive call take place for 8 numbers?
MergeSort(0,7);

• MergeSort(0,3);

------------MergeSort(0,1)
------------------------ MergeSort(0,0) ... now returns
------------------------MergeSort(1,1) ... now returns
------------------------Merge() the very first merge after 6 calls to MergeSort ??
------------MergeSort(2,3)
------------------------MergeSort(2,2) ... now returns
------------------------MergeSort(3,3) ... now returns
------------------------Merge()
------------Merge()

• MergeSort(4,7);

------------MergeSort(4,5)
------------------------MergeSort(4,4) ... now returns
------------------------MergeSort(5,5) ... now returns
------------------------Merge()
------------MergeSort(6,7)
------------------------MergeSort(6,6) ... now returns
------------------------MergeSort(7,7) ... now returns
------------------------Merge()
------------Merge()

• Merge() .. final two merge the two halves

15 steps for 8 numbers



Check out wiki link : Merge Sort or the SortExplain Workbook in Excel