MergeSort

gistfile1.cs

using System;
using System.Collections.Generic;
using System.Text;
using System.Collections;

    public class MergeSorter
    {

        public static List<T> MergeSort<T>(List<T> list) where T : IComparable<T>
        {
            if (list.Count == 1)
            {
                return list;
            }

            List<T> sorted = new List<T>();
            int middle = (int)list.Count / 2;
            List<T> left = list.GetRange(0, middle);
            List<T> right = list.GetRange(middle, list.Count - middle);
            left = MergeSort<T>(left);
            right = MergeSort(right);
            int leftptr = 0;
            int rightptr = 0;
            for (int i = 0; i < left.Count + right.Count; i++)
            {
                if (leftptr == left.Count)
                {
                    sorted.Add(right[rightptr]);
                    rightptr++;
                }
                else if(rightptr == right.Count)
                {
                    sorted.Add(left[leftptr]);
                    leftptr++;
                }
                else if (left[leftptr].CompareTo(right[rightptr]) < 0)
                {
                    sorted.Add(left[leftptr]);
                    leftptr++;
                }
                else
                {
                    sorted.Add(right[rightptr]);
                    rightptr++;
                }

            }
            return sorted;
        }

        
    }