SHARE
TWEET

MergeSort

a guest Jul 1st, 2013 323 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. private IList<T> MergeSort(IList<T> collection)
  2. {
  3.     if (collection.Count <= 1)
  4.     {
  5.         return collection;
  6.     }
  7.  
  8.     int middle = (collection.Count) / 2;
  9.  
  10.     IList<T> left = new List<T>();
  11.     IList<T> right = new List<T>();
  12.  
  13.     for (int i = 0; i < middle; i++)
  14.     {
  15.         left.Add(collection[i]);
  16.     }
  17.  
  18.     for (int i = middle; i < collection.Count; i++)
  19.     {
  20.         right.Add(collection[i]);
  21.     }
  22.  
  23.     left = MergeSort(left);
  24.     right = MergeSort(right);
  25.  
  26.     return Merge(left, right);
  27. }
  28.  
  29. private IList<T> Merge(IList<T> left, IList<T> right)
  30. {
  31.     IList<T> collectionMerge = new List<T>();
  32.  
  33.     while (left.Count > 0 || right.Count > 0)
  34.     {
  35.         if (left.Count > 0 && right.Count > 0)
  36.         {
  37.             if (left[0].CompareTo(right[0]) <= 0)
  38.             {
  39.                 AddFirstItemAndResizeSubCollection(collectionMerge, ref left);
  40.             }
  41.             else
  42.             {
  43.                 AddFirstItemAndResizeSubCollection(collectionMerge, ref right);
  44.             }
  45.         }
  46.         else if (left.Count > 0)
  47.         {
  48.             AddFirstItemAndResizeSubCollection(collectionMerge, ref left);
  49.         }
  50.         else if (right.Count > 0)
  51.         {
  52.             AddFirstItemAndResizeSubCollection(collectionMerge, ref right);
  53.         }
  54.     }
  55.  
  56.     return collectionMerge;
  57. }
  58.  
  59. private void AddFirstItemAndResizeSubCollection(IList<T> collection, ref IList<T> subCollection)
  60. {
  61.     collection.Add(subCollection[0]);
  62.     subCollection = GetRest(subCollection);
  63. }
  64.  
  65. private IList<T> GetRest(IList<T> collection)
  66. {
  67.     IList<T> rest = new List<T>();
  68.  
  69.     for (int i = 1; i < collection.Count; i++)
  70.     {
  71.         rest.Add(collection[i]);
  72.     }
  73.  
  74.     return rest;
  75. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top