List и различие IEnumerable

Реализуя эту общую сортировку слиянием , как своего рода Code Kata , я наткнулся на разницу между IEnumerable и List, и мне нужна помощь чтобы выяснить.

Вот MergeSort

public class MergeSort
{
    public IEnumerable Sort(IEnumerable arr)
    {
        if (arr.Count() <= 1) return arr;

        int middle = arr.Count() / 2;
        var left = arr.Take(middle).ToList();
        var right = arr.Skip(middle).ToList();
        return Merge(Sort(left), Sort(right));
    }

    private static IEnumerable Merge(IEnumerable left, IEnumerable right)
    {
        var arrSorted = new List();

        while (left.Count() > 0 && right.Count() > 0)
        {
            if (Comparer.Default.Compare(left.First(), right.First()) < 0)
            {
                arrSorted.Add(left.First());
                left=left.Skip(1);
            }
            else
            {
                arrSorted.Add(right.First());  
                right=right.Skip(1);  
            }
        }

        return arrSorted.Concat(left).Concat(right);
    }
}

Если я удалю .ToList () в левой и правой переменных, она не сможет правильно отсортировать . Вы понимаете, почему?

Пример

var ints = new List { 5, 8, 2, 1, 7 };
var mergeSortInt = new MergeSort();
var sortedInts = mergeSortInt.Sort(ints);

С . ToList ()

    [0]: 1
    [1]: 2
    [2]: 5
    [3]: 7
    [4]: 8

Без .ToList ()

    [0]: 1
    [1]: 2
    [2]: 5
    [3]: 7
    [4]: 2

Edit

Меня поразил мой глупый тест.

Я тестировал его так:

var sortedInts = mergeSortInt.Sort(ints);
ints.Sort();
if (Enumerable.SequenceEqual(ints, sortedInts)) Console.WriteLine("ints sorts ok");

просто заменил первую строку на

var sortedInts = mergeSortInt.Sort(ints).ToList();

устраняет проблему (и ленивую оценку).

РЕДАКТИРОВАТЬ 2010-12-29

Я думал, что пойму, как ленивая оценка здесь все портит, но я просто не понимаю.

Удалите .ToList () в методе сортировки выше, например

var left = arr.Take(middle);
var right = arr.Skip(middle);

, затем попробуйте это

var ints = new List { 5, 8, 2 };
var mergeSortInt = new MergeSort();
var sortedInts = mergeSortInt.Sort(ints);
ints.Sort();
if (Enumerable.SequenceEqual(ints, sortedInts)) Console.WriteLine("ints sorts ok");

При отладке Вы можете увидеть, что до ints.Sort () a sortedInts.ToList () возвращает

[0]: 2
[1]: 5
[2]: 8

, но после ints.Sort () он возвращает

[0]: 2
[1]: 5
[2]: 5

Что здесь на самом деле происходит?