ArrayList.Sort debe ser un tipo estable con un IComparer pero no lo es?

Question

A stable sort es un tipo que mantiene el orden relativo de los elementos con el mismo valor.

Los documentos sobre ArrayList.Sort dicen que cuando se proporciona un IComparer el tipo es estable:

Si comparador se pone a cero, este método realiza una comparación de orden (también llamado un tipo inestable); es decir, si dos elementos son iguales, es posible que su orden no se conserve. Por el contrario, un género estable conserva el orden de los elementos que son iguales. Para realizar una clasificación estable, debe implementar una interfaz IComparer personalizada.

A menos que me falta algo, el siguiente caso de prueba muestra que ArrayList.Sort no está utilizando una especie estable:

internal class DisplayOrdered { 
    public int ID { get; set; } 
    public int DisplayOrder { get; set; } 
    public override string ToString() { 
     return string.Format("ID: {0}, DisplayOrder: {1}", ID, DisplayOrder); 
    } 
} 

internal class DisplayOrderedComparer : IComparer { 
    public int Compare(object x, object y) { 
     return ((DisplayOrdered)x).DisplayOrder - ((DisplayOrdered)y).DisplayOrder; 
    } 
} 

[TestFixture] 
public class ArrayListStableSortTest { 

    [Test] 
    public void TestWeblinkCallArrayListIsSortedUsingStableSort() { 
     var call1 = new DisplayOrdered {ID = 1, DisplayOrder = 0}; 
     var call2 = new DisplayOrdered {ID = 2, DisplayOrder = 0}; 
     var call3 = new DisplayOrdered {ID = 3, DisplayOrder = 2}; 
     var list = new ArrayList {call1, call2, call3}; 

     list.Sort(new DisplayOrderedComparer()); 

     // expected order (by ID): 1, 2, 3 (because the DisplayOrder 
     // is equal for ID's 1 and 2, their ordering should be 
     // maintained for a stable sort.) 
     Assert.AreEqual(call1, list[0]); // Actual: ID=2 ** FAILS 
     Assert.AreEqual(call2, list[1]); // Actual: ID=1 
     Assert.AreEqual(call3, list[2]); // Actual: ID=3 
    } 
} 

Me estoy perdiendo algo? De lo contrario, ¿se trataría de un error de documentación o de una biblioteca?

Al parecer, utilizando un OrderBy en Linq da un tipo estable.

Answer 1

Lo que la documentación parece indicar es que la única forma de obtener una clasificación estable con ArrayList.Sort es usar IComparer que de alguna manera "conoce" los índices de los artículos que se comparan (uno podría imaginarse logrando esto haciendo que ejecute un pase inicial en la colección) y usa esa información como un desempate para elementos que de otro modo serían iguales.

Aunque estoy de acuerdo que la redacción de la documentación deja mucho que desear, lo que realmente no tiene sentido que cualquier comparador de edad que no en cuenta los índices de los artículos a ser comparado mágicamente puede convertir una intrínsecamente algoritmo de clasificación inestable (que es lo que Arraylist.Sort) es estable.