c# - ArrayList.Sort should be a stable sort with an IComparer but is not? -

a stable sort sort maintains relative ordering of elements same value.

the docs on arraylist.sort when icomparer provided sort stable:

if comparer set null, method performs comparison sort (also called unstable sort); is, if 2 elements equal, order might not preserved. in contrast, stable sort preserves order of elements equal. perform stable sort, must implement custom icomparer interface.

unless i'm missing something, following testcase shows arraylist.sort not using stable sort:

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 displayorder         // equal id's 1 , 2, ordering should         // maintained 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     } } 

am missing something? if not, documentation bug or library bug?

apparently using orderby in linq gives stable sort.

what documentation appears saying way can stable sort arraylist.sort use icomparer somehow 'knows' indices of items being compared (one imagine accomplishing making run initial pass on collection) , uses information tie-breaker otherwise equal elements.

although agree phrasing of documentation leaves desired, doesn't make sense old comparer doesn't consider indices of items compared can magically turn inherently unstable sorting algorithm (which arraylist.sort is) stable one.