Ben Foster - 1 year ago 82
C# Question

# Efficiently sort an IList<T> without copying the source list

Given the test case below how can I:

1. Sort the
`IList<TestObject>`
based on the index of a matching
`Id`

in the
`IList<int>`
list.

2. Unmatched values are moved to the end of the list and sorted by their original index. In this case, since 3 and 4 do not exist in the index list, we expect to see
`list[3] == 3`
and
`list[4] == 4`
.

3. Whilst I know this can be achieved with linq, I need to resort the original list rather than creating a new one (due to how the list is stored).

4. The source list must be an
`IList`
(I can't use
`List<T>`
)

Here's the test:

``````    public class TestObject
{
public int Id { get; set; }
}

[Test]
public void Can_reorder_using_index_list()
{
IList<TestObject> list = new List<TestObject>
{
new TestObject { Id = 1 },
new TestObject { Id = 2 },
new TestObject { Id = 3 },
new TestObject { Id = 4 },
new TestObject { Id = 5 }
};

IList<int> indexList = new[] { 10, 5, 1, 9, 2 };

// TODO sort

Assert.That(list[0].Id, Is.EqualTo(5));
Assert.That(list[1].Id, Is.EqualTo(1));
Assert.That(list[2].Id, Is.EqualTo(2));
Assert.That(list[3].Id, Is.EqualTo(3));
Assert.That(list[4].Id, Is.EqualTo(4));
}
``````

Update:

As requested, this is what I did try, but 1) it only works with
`List<T>`
and 2) I'm not sure it's the most efficient way:

``````       var clone = list.ToList();
list.Sort((x, y) =>
{
var xIndex = indexList.IndexOf(x.Id);
var yIndex = indexList.IndexOf(y.Id);

if (xIndex == -1)
{
xIndex = list.Count + clone.IndexOf(x);
}
if (yIndex == -1)
{
yIndex = list.Count + clone.IndexOf(y);
}

return xIndex.CompareTo(yIndex);
});
``````

Update 2:

Thanks to @leppie, @jamiec, @mitch wheat - this is the working code:

``````    public class TestObjectComparer : Comparer<TestObject>
{

public TestObjectComparer(IList<int> indexList, Func<TestObject, int> currentIndexFunc, int listCount)
{
this.indexList = indexList;
this.currentIndexFunc = currentIndexFunc;
this.listCount = listCount;
}

public override int Compare(TestObject x, TestObject y)
{
var xIndex = indexList.IndexOf(x.Id);
var yIndex = indexList.IndexOf(y.Id);

if (xIndex == -1)
{
xIndex = listCount + currentIndexFunc(x);
}
if (yIndex == -1)
{
yIndex = listCount + currentIndexFunc(y);
}

return xIndex.CompareTo(yIndex);
}
}

[Test]
public void Can_reorder_using_index_list()
{
IList<TestObject> list = new List<TestObject>
{
new TestObject { Id = 1 },
new TestObject { Id = 2 },
new TestObject { Id = 3 },
new TestObject { Id = 4 },
new TestObject { Id = 5 }
};

IList<int> indexList = new[] { 10, 5, 1, 9, 2, 4 };

ArrayList.Adapter((IList)list).Sort(new TestObjectComparer(indexList, x => list.IndexOf(x), list.Count));

Assert.That(list[0].Id, Is.EqualTo(5));
Assert.That(list[1].Id, Is.EqualTo(1));
Assert.That(list[2].Id, Is.EqualTo(2));
Assert.That(list[3].Id, Is.EqualTo(3));
Assert.That(list[4].Id, Is.EqualTo(4));
}
``````

Been looking at this for a bit, and indeed as previously said, your going to need ArrayList.Adapter, however you'll note it takes a non-generic IList so some casting will be required:

``````ArrayList.Adapter((IList)list)
``````

You'll also need to write a comparer, of which the logic to do your sorting willl be contained. Excuse the name but:

``````public class WeirdComparer : IComparer,IComparer<TestObject>
{
private IList<int> order;
public WeirdComparer(IList<int> order)
{
this.order = order;
}
public int Compare(object x, object y)
{
return Compare((TestObject) x, (TestObject) y);
}

public int Compare(TestObject x, TestObject y)
{
if(order.Contains(x.Id))
{
if(order.Contains(y.Id))
{
return order.IndexOf(x.Id).CompareTo(order.IndexOf(y.Id));
}
return -1;
}
else
{
if (order.Contains(y.Id))
{
return 1;
}
return x.Id.CompareTo(y.Id);
}
}
}
``````

EDIT: Added implementation to above comparerr

Then the usage would be as follows:

``````IList<int> indexList = new[] { 10, 5, 1, 9, 2 };