SHARE
TWEET

Arrays.13.MergeSort

Teodor92 Jan 21st, 2013 291 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. /* * Write a program that sorts an array of
  2.  * integers using the merge sort algorithm
  3.  * (find it in Wikipedia).
  4.  */
  5.  
  6. using System;
  7. using System.Collections.Generic;
  8.  
  9. class MergeSort
  10. {
  11.     static List<int> MergeSortAlg(List<int> unsortedList)
  12.     {
  13.         if (unsortedList.Count <= 1)
  14.         {
  15.             return unsortedList;
  16.         }
  17.         List<int> left = new List<int>();
  18.         List<int> right = new List<int>();
  19.         int middle = unsortedList.Count / 2;
  20.         for (int i = 0; i < middle; i++)
  21.         {
  22.             left.Add(unsortedList[i]);
  23.         }
  24.         for (int i = middle; i < unsortedList.Count; i++)
  25.         {
  26.             right.Add(unsortedList[i]);
  27.         }
  28.         left = MergeSortAlg(left);
  29.         right = MergeSortAlg(right);
  30.         return Merge(left,right);
  31.  
  32.     }
  33.     static List<int> Merge(List<int> left, List<int> right)
  34.     {
  35.         List<int> result = new List<int>();
  36.         while (left.Count > 0 || right.Count > 0)
  37.         {
  38.             if (left.Count > 0 && right.Count > 0)
  39.             {
  40.                 if (left[0] <= right[0])
  41.                 {
  42.                     result.Add(left[0]);
  43.                     left.RemoveAt(0);
  44.                 }
  45.                 else
  46.                 {
  47.                     result.Add(right[0]);
  48.                     right.RemoveAt(0);
  49.                 }
  50.             }
  51.             else if (left.Count > 0)
  52.             {
  53.                 result.Add(left[0]);
  54.                 left.RemoveAt(0);
  55.             }
  56.             else if (right.Count > 0)
  57.             {
  58.                 result.Add(right[0]);
  59.                 right.RemoveAt(0);
  60.             }
  61.         }
  62.         return result;
  63.     }
  64.     static void Main()
  65.     {
  66.         List<int> array = new List<int> { 2, 3, 5, 0, 123, 3, 23, 1234, 87 };
  67.         List<int> sortedArray = MergeSortAlg(array);
  68.         foreach (var item in sortedArray)
  69.         {
  70.             Console.Write("{0} ", item);
  71.         }
  72.         Console.WriteLine();
  73.     }
  74. }
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
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!
 
Top