Merge sort

Posted By on September 2, 2014

Merge-sort is based on the divide-and-conquer paradigm. It involves the following three steps:

• Divide the array into two (or more) subarrays
• Sort each subarray (Conquer)
• Merge them into one (in a smart way!)

Example. Consider the following array of numbers

`27  10  12  25  34  16  15  31`

divide it into two parts

`27  10  12  25            34  16  15  31`

divide each part into two parts

`27  10            12  25            34  16            15  31`

divide each part into two parts

`27       10       12       25       34       16       15       31`

merge (cleverly-!) parts

`10  27            12  25            16  34            15  31`

merge parts

`10  12  25  27                 15  16  31  34`

merge parts into one

`10  12  15  16  25  27  31  34`

How do we merge two sorted subarrays? We define three references at the front of each array.

We keep picking the smallest element and move it to a temporary array, incrementing the corresponding indices.

Complexity of Mergesort

Suppose T(n) is the number of comparisons needed to sort an array of n elements by the MergeSort algorithm. By splitting an array in two parts we reduced a problem to sorting two parts but smaller sizes, namely n/2. Each part can be sort in T(n/2). Finally, on the last step we perform n-1 comparisons to merge these two parts in one. All together, we have the following equation

` T(n) = 2*T(n/2) + n - 1 `

The solution to this equation is beyond the scope of this course. However I will give you a resoning using a binary tree. We visualize the mergesort dividing process as a tree

Posted by Akash Kurup

Founder and C.E.O, World4Engineers Educationist and Entrepreneur by passion. Orator and blogger by hobby

Website: http://world4engineers.com