Merge sort is a comparison-based sorting algorithm. It is based on divide-and-conquer paradigm. Most implementations produce a stable sort, which means that the implementation preserves the input order of equal elements in the sorted output.

For more information about Merge Sort Algorithm:
http://en.wikipedia.org/wiki/Merge_sort

Implementation and Usage:

            int[] arr = new int[10]
            {
                1, 5, 4, 11, 20, 8, 2, 98, 90, 16
            };

            MergeSort(arr, 0, arr.Length - 1);
            Console.WriteLine("Sorted Values:");
            for (int i = 0; i < arr.Length; i++)
                Console.WriteLine(arr[i]);

            //Output:
            //Sorted Values:
            //1
            //2
            //4
            //5
            //8
            //11
            //16
            //20
            //90
            //98

        private void Merge(int[] input, int left, int middle, int right)
        {
            int[] leftArray = new int[middle - left + 1];
            int[] rightArray = new int[right - middle];

            Array.Copy(input, left, leftArray, 0, middle - left + 1);
            Array.Copy(input, middle + 1, rightArray, 0, right - middle);

            int i = 0;
            int j = 0;
            for (int k = left; k < right + 1; k++)
            {
                if (i == leftArray.Length)
                {
                    input[k] = rightArray[j];
                    j++;
                }
                else if (j == rightArray.Length)
                {
                    input[k] = leftArray[i];
                    i++;
                }
                else if (leftArray[i] <= rightArray[j])
                {
                    input[k] = leftArray[i];
                    i++;
                }
                else
                {
                    input[k] = rightArray[j];
                    j++;
                }
            }
        }

        private void MergeSort(int[] input, int left, int right)
        {
            if (left < right)
            {
                int middle = (left + right) / 2;

                MergeSort(input, left, middle);
                MergeSort(input, middle + 1, right);

                Merge(input, left, middle, right);
            }
        }    

See Also:

• Selection Sort Algorithm
• Insertion Sort Algorithm
• Bubble Sort Algorithm
• Counting Sort Algorithm
• Quick Sort Algorithm