Merge sort

Posted By on September 2, 2014


Download PDF
Insertion Sort
Binary Search Tree

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

Insertion Sort
Binary Search Tree

Download PDF

Posted by Akash Kurup

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

Website: http://world4engineers.com