Thursday, January 15, 2015

MergeSort study

MergeSort algorithm learning notes:

I am studying algorithm course in coursera to sharpen my CS understanding.

Karatsuba algorithm (KA) is the first algorithm in this course opened my eyes. I never thought of any faster algorithm can do better/faster than the grade 3 learned calculating algorithm. I plan to implement KA in another thread in C# and post it here.

Back to track, this thread is about MergeSort algorithm (MA). Teacher Tim Roughgarden introduced the MA with a simple example and illustrate further step by step why MA is faster than most of other O(n2) algorithm. 

Here is MA's sorting complexity explanation:

  • Each level of MA calculation has maxi. 6j operations, given that j is the number of items in the current level array input in each recursive call). 
  • MA has sum of log2(n) + 1 levels (assume original level is level 0)
  • At any given level j, there are 2^j (2pwoer j) number of recursive calls
  • At any given level j, each recursive call  has array size n/2^j
We find out that the operations at any given level j is 2^j * (6 *n/2^j) = 6n (astonishingly independent of j ! isn't this cool!?)

Finally, 6n (log2(n) + 1) is the total operations in MA.

In summary, the reason Mergesort is fast is that its operations in each call is constant 6n and the level of recursive call is log2(n), which is flatter than f(n) = n. The drawback for mergesort is that it requires extra space to store the items when aggregating back from the left and right sub-streams.

C# implementation
 using System;  
 using System.Linq;  
 namespace Mergesort  
   class Program  
     static void Main(string[] args)  
       Console.WriteLine("please give a integer for the size of array, system will generate internal values and do sorting for you");  
       int size = int.Parse(Console.ReadLine());  
       Random random = new Random();  
       int randomInt;  
       int[] count = new int[size];  
       for (int i = 0; i < size; i++)   
         randomInt = random.Next(0, size);  
         count[i] = randomInt;  
       int[] countResult = Mergesort(count);  
       foreach (int i in countResult)  
       { Console.WriteLine(i); }  
     public static int[] Mergesort(int[] A)  
       if (A.Length == 1)  
         return A;  
       int size = A.Length;  
       int halfSize = A.Length / 2;  
       int[] A1 = new int[halfSize];  
       int[] A2 = new int[A.Length - halfSize];  
       Split<int>(A, halfSize, out A1, out A2);  
       int[] ResultA = Mergesort(A1);  
       int[] ResultB = Mergesort(A2);  
       return MergeTwoArray(ResultA, ResultB);  
     private static int[] MergeTwoArray(int[] ResultA, int[] ResultB)  
       int resultSize = ResultA.Length + ResultB.Length;  
       int[] resultArray = new int[resultSize];  
       int i = 0, j = 0;  
       for (int k = 0; k < resultSize; k++)  
         if (i == ResultA.Length)  
           resultArray[k] = ResultB[j++];  
         else if (j == ResultB.Length)  
           resultArray[k] = ResultA[i++];  
         else if (ResultA[i] <= ResultB[j])  
           resultArray[k] = ResultA[i++];  
           resultArray[k] = ResultB[j++];  
       return resultArray;  
     public static void Split<T>(T[] array, int index, out T[] first, out T[] second)  
       first = array.Take(index).ToArray();  
       second = array.Skip(index).ToArray();  

No comments:

Post a Comment