Data Structures-Merge Sort

Merge Sort

Merge sort is a sorting technique that divides the array into equal halves and then sorts them together.

How does merge sort work?

Let us take the example of the following unsorted array:

14, 33, 27, 10, 35, 19, 42, 44.

Merge sort divides the entire array iteratively into two equal halves.

So the array above is divided as follows:

14, 33, 27, 10 and 35, 19, 42, 44.

Now it is divided into pairs:

14, 33; 27, 10; 35, 19; 42, 44.

Then are divided into single numbers:

14, 33, 27, 10, 35, 19, 42, 44.

Now they are combined as they were broken down, only after comparing every pair.

So in the end the sorted array will be:

10, 14, 19, 27, 33, 35, 42, 44.

Pseudocode

procedure mergesort( var a as array )
   if ( n == 1 ) return a
   var l1 as array = a[0] ... a[n/2]
   var l2 as array = a[n/2+1] ... a[n]
   l1 = mergesort( l1 )
   l2 = mergesort( l2 )
   return merge( l1, l2 )
end procedure
procedure merge( var a as array, var b as array )
   var c as array
   while ( a and b have elements )
      if ( a[0] > b[0] )
         add b[0] to the end of c
         remove b[0] from b
      else
         add a[0] to the end of c
         remove a[0] from a
      end if
   end while
   
   while ( a has elements )
      add a[0] to the end of c
      remove a[0] from a
   end while
   
   while ( b has elements )
      add b[0] to the end of c
      remove b[0] from b
   end while
   
   return c
end procedure

Reference

Merge Sort