Learn Computer Science programming - C# and C++ Algorithms

 
Merge Sort

The merge sort splits the list to be sorted into two equal halves and places them two arrays. A third array is used to store the sorted results. It then sorts each array and then merges them back together. The algorithm is complex O(n log n), highly recursive. The merge sort can be written in a non-recursive code, but it does not have the same performance advantage. It is slightly faster than the heap sort for larger data, but requires double the memory compared to other sorts.
Code
c_merge_sort.zip
File Size: 23 kb
File Type: zip
Download File

using System;
using System.Collections;

namespace MergeSort
{
    public class SortShell
    {
        /// <summary>
        /// The main entry point for the application.
        /// </summary>
        [STAThread]
        static void Main(string[] args)
        {
            int[] numbers = new int[] { 3, 4, 65, 7, 8, 11, 2234, 4, 117 };
            int i, j, tmp, n;
            n = numbers.Length;
            Console.WriteLine("Before");
            Display(numbers);
            MergeSort(numbers);
            Console.WriteLine("\r\nAfter");
            Display(numbers);
        }

        public static int[] MergeSort(int[] array)
        {
   if(array.Length > 1)
   {
   int elementsInArray1 = array.Length/2;
   int elementsInArray2 = elementsInArray1;
   
            if((array.Length % 2) == 1)
   elementsInArray2 += 1;
   
            int []array1 = new int[elementsInArray1];
   int []array2 = new int[elementsInArray2];

   for(int i = 0; i < elementsInArray1; i++)
   array1[i] = array[i];

   for(int i = elementsInArray1; i < elementsInArray1 + elementsInArray2; i++)
   array2[i - elementsInArray1] = array[i];
   
            array1 = MergeSort(array1);
   array2 = MergeSort(array2);
   
            int ii = 0, j = 0, k = 0;
   while(array1.Length != j && array2.Length != k)
   {
   if(array1[j] < array2[k])
   {
   array[ii] = array1[j];
   ii++;
   j++;
   }
   else
   {
   array[ii] = array2[k];
   ii++;
   k++;
   }
   }

   while(array1.Length != j)
   {
   array[ii] = array1[j];
   ii++;
   j++;
   }
   while(array2.Length != k)
   {
   array[ii] = array2[k];
   ii++;
   k++;
   }
   }
   return array;
    }


        static void Display(int[] numbers)
        {
            //Display Array Content
            IEnumerator sorted = numbers.GetEnumerator();
            while (sorted.MoveNext())
            {
                Console.WriteLine(sorted.Current);
            }
        }
    }
}