Created
June 17, 2014 14:41
-
-
Save emoacht/0f79b1dc3308d2c7caf4 to your computer and use it in GitHub Desktop.
A draft of enumerable merge sort method
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
private const int countThreshold = 64; | |
public static IEnumerable<TSource> MergeSort<TSource, TKey>(this IEnumerable<TSource> source, Func<TSource, TKey> keySelector) | |
{ | |
if (source == null) | |
throw new ArgumentNullException("source"); | |
var countFull = source.Count(); | |
if (countFull < countThreshold) | |
return source.OrderBy(keySelector); | |
int countHalf = countFull / 2; | |
var firstHalf = source.Take(countHalf).MergeSort(keySelector); | |
var secondHalf = source.Skip(countHalf).MergeSort(keySelector); | |
return firstHalf.Merge(secondHalf, keySelector); | |
} | |
public static IEnumerable<TSource> Merge<TSource, TKey>(this IEnumerable<TSource> first, IEnumerable<TSource> second, Func<TSource, TKey> keySelector) | |
{ | |
if (first == null) | |
throw new ArgumentNullException("first"); | |
if (second == null) | |
throw new ArgumentNullException("second"); | |
var comparer = Comparer<TKey>.Default; | |
using (var firstEnumerator = first.GetEnumerator()) | |
using (var secondEnumerator = second.GetEnumerator()) | |
{ | |
bool firstMoved = firstEnumerator.MoveNext(); | |
bool secondMoved = secondEnumerator.MoveNext(); | |
while (firstMoved && secondMoved) | |
{ | |
if (comparer.Compare(keySelector(firstEnumerator.Current), keySelector(secondEnumerator.Current)) <= 0) | |
{ | |
yield return firstEnumerator.Current; | |
firstMoved = firstEnumerator.MoveNext(); | |
} | |
else | |
{ | |
yield return secondEnumerator.Current; | |
secondMoved = secondEnumerator.MoveNext(); | |
} | |
} | |
while (firstMoved) | |
{ | |
yield return firstEnumerator.Current; | |
firstMoved = firstEnumerator.MoveNext(); | |
} | |
while (secondMoved) | |
{ | |
yield return secondEnumerator.Current; | |
secondMoved = secondEnumerator.MoveNext(); | |
} | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment