Last active
August 6, 2017 05:52
-
-
Save valiyo/4641642 to your computer and use it in GitHub Desktop.
C# interpretation of the top-down implementation of Merge Sort from Wikipedia:
http://en.wikipedia.org/wiki/Merge_sort
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
using System; | |
using System.Collections.Generic; | |
using System.Linq; | |
/* Write a program that sorts an array of integers | |
* using the merge sort algorithm (find it in Wikipedia). */ | |
class MergeSortAlgorithm | |
{ | |
public static int[] MergeSort(int[] array) | |
{ | |
// If list size is 0 (empty) or 1, consider it sorted and return it | |
// (using less than or equal prevents infinite recursion for a zero length array). | |
if (array.Length <= 1) | |
{ | |
return array; | |
} | |
// Else list size is > 1, so split the list into two sublists. | |
int middleIndex = (array.Length) / 2; | |
int[] left = new int[middleIndex]; | |
int[] right = new int[array.Length - middleIndex]; | |
Array.Copy(array, left, middleIndex); | |
Array.Copy(array, middleIndex, right, 0, right.Length); | |
// Recursively call MergeSort() to further split each sublist | |
// until sublist size is 1. | |
left = MergeSort(left); | |
right = MergeSort(right); | |
// Merge the sublists returned from prior calls to MergeSort() | |
// and return the resulting merged sublist. | |
return Merge(left, right); | |
} | |
public static int[] Merge(int[] left, int[] right) | |
{ | |
// Convert the input arrays to lists, which gives more flexibility | |
// and the option to resize the arrays dynamically. | |
List<int> leftList = left.OfType<int>().ToList(); | |
List<int> rightList = right.OfType<int>().ToList(); | |
List<int> resultList = new List<int>(); | |
// While the sublist are not empty merge them repeatedly to produce new sublists | |
// until there is only 1 sublist remaining. This will be the sorted list. | |
while (leftList.Count > 0 || rightList.Count > 0) | |
{ | |
if (leftList.Count > 0 && rightList.Count > 0) | |
{ | |
// Compare the 2 lists, append the smaller element to the result list | |
// and remove it from the original list. | |
if (leftList[0] <= rightList[0]) | |
{ | |
resultList.Add(leftList[0]); | |
leftList.RemoveAt(0); | |
} | |
else | |
{ | |
resultList.Add(rightList[0]); | |
rightList.RemoveAt(0); | |
} | |
} | |
else if (leftList.Count > 0) | |
{ | |
resultList.Add(leftList[0]); | |
leftList.RemoveAt(0); | |
} | |
else if (rightList.Count > 0) | |
{ | |
resultList.Add(rightList[0]); | |
rightList.RemoveAt(0); | |
} | |
} | |
// Convert the resulting list back to a static array | |
int[] result = resultList.ToArray(); | |
return result; | |
} | |
static void Main() | |
{ | |
int[] array = new int[] { 5, 2, 6, 4, 7, 10, 1, 9, 3, 8 }; | |
array = MergeSort(array); | |
// Print the sorted list | |
for (int index = 0; index < array.Length; index++) | |
{ | |
Console.WriteLine("element[{0}] = {1}", index, array[index]); | |
} | |
Console.WriteLine(); | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
Thanks , perfectly right implementation.