Skip to content

Instantly share code, notes, and snippets.

@emoacht
Created June 17, 2014 14:41
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save emoacht/0f79b1dc3308d2c7caf4 to your computer and use it in GitHub Desktop.
Save emoacht/0f79b1dc3308d2c7caf4 to your computer and use it in GitHub Desktop.
A draft of enumerable merge sort method
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