Tuesday, July 09, 2013

Интересное поведение сортировки в .NET

  Всё началось с того, что на работе у коллеги стали падать тесты. Причём только у неё одной. Вдаваться в подробности не буду, но суть в том, что в тесте было два объекта List. Первый был эталонным, а второй — возвращался тестируемым методом. Затем листы сравнивались поэлементно.

   Очень быстро было выяснена причина падения теста: у коллеги порядок элементов в результирующем массиве был обратным порядку в эталонном массиве. В коде тестируемого метода использовался стандартный List.Sort с нашим компаратором, который именно на этом тесте всегда возвращает 0. Но у всей команды элементы возвращались в одном порядке, а у одной сотрудницы — строго в обратном. Было быстро выяснено, что у коллеги давно не было обновлений и версия mscorlib.dll у неё сильно отличалась от той, что была у остальных. На этом можно было бы и успокоиться, но мне стало интересно я решил копать дальше и вот что выяснил. 

   Содержимое листа после сортировки и до при одинаковых элементах может отличаться, т.к. согласно msdn в list.sort используется QuickSort, которая, как мы все прекрасно знаем, неустойчива. Однако есть одна интересная особенность. О ней дальше.

Возьмём такой код:
Код
using System;
using System.Collections.Generic;

namespace fkComparer {
    internal struct Smth {
        public int X;
        public int Y;
    }

    internal class SmthComparer : IComparer<Smth> {
        #region Implementation of IComparer<in smth>
        public int Compare(Smth x, Smth y) {
            Result.Count++;
            if(x.Y < y.Y)
                return -1;
            if(x.Y > y.Y)
                return 1;
            return 0;
        }