Sorting IList<T> *in place*

[Marcel Müller]

Is there a way to sort an IList<T> in place?

The solutions I found imply that you copy the current list to List<T>,
sort it and throw away the current IList<T> by replacing the reference
with a new list.

But this might be a very bad Idea if the IList<T> have been something
else than a simple List<T> before. Furthermore it requires by reference
access to the list parameter.

OK, I could copy the list, sort it, clear the original list and copy the
sorted content back to the original list. Seriously?

Isn't there any generic sort algorithm that can be applied to a generic
interface?


Marcel

[Peter Duniho]

On Wed, 25 Jul 2012 15:21:54 +0200, Marcel Müller wrote:

> Is there a way to sort an IList<T> in place?

Sure, as long as it's not a read-only IList<T>. Of course there is.

Now, there's nothing in .NET that I know of that will do that. The built-in
sort implementations apply to arrays or List<T> instances. But there's
nothing stopping you from writing your own.

Indeed, it's possible that someone has already done so. The built-in .NET
sort algorithms use quicksort, which is great for many scenarios, but not
the most efficient in others. Even ignoring IList<T> there's good reason to
have alternatives, so in any case maybe it's already been done.

You should use your favorite web search engine to look for a third-party
library that does that. Even if it doesn't support IList<T> directly, with
an open-source library it would be easy enough to port the existing
algorithm to do so.

Heck...Arne seems to have lots of free time. Maybe he'll even write it for
you and post it here. :) It wouldn't even actually be that many lines of
code...it's just a matter of writing it down.

In the meantime, I recommend you take a look at these articles, with an eye
toward just writing it yourself:

http://en.wikipedia.org/wiki/Quicksort
http://en.wikipedia.org/wiki/Heapsort

Those are two of the best general-purpose sorts, both of which can be
implemented to be both memory- and time-efficient.

Pete

[Arne Vajhøj]

I would be skeptical about its usage, because IList does only
guarantee that elements can be accessed by index not that such
access will be efficient, so if access by index is O(n) instead
of O(1) performance will be very bad.

But a quicksort of IList<T> is easy to write.

Simple version:

public class QS
{
private static void SortHelp<T>(int n1, int n2, IList<T> lst)
where T : IComparable<T>
{
int l = n1;
int r = n2;
T pivot = lst[(n1 + n2) / 2];
do
{
while (lst[l].CompareTo(pivot) < 0) l++;
while (lst[r].CompareTo(pivot) > 0) r--;
if (l <= r)
{
T tmp = lst[l];
lst[l] = lst[r];
lst[r] = tmp;
l++;
r--;
}
} while (l <= r);
if (n1 < r) SortHelp(n1, r, lst);
if (l < n2) SortHelp(l, n2, lst);
return;
}
public static void Sort<T>(IList<T> lst) where T : IComparable<T>
{
SortHelp(0, lst.Count - 1, lst);
}
}

Arne

[Marcel Müller]

On 25.07.2012 16:26, Peter Duniho wrote:
>> Is there a way to sort an IList<T> in place?
>
> Sure, as long as it's not a read-only IList<T>. Of course there is.
>
> Now, there's nothing in .NET that I know of that will do that. The built-in
> sort implementations apply to arrays or List<T> instances. But there's
> nothing stopping you from writing your own.

Oh, that's the point that I wanted to avoid.
It's unbelievable that business applications that use a modern
development environment need to ship with their own general purpose sort
algorithmn, isn't it?.

> You should use your favorite web search engine to look for a third-party
> library that does that. Even if it doesn't support IList<T> directly, with
> an open-source library it would be easy enough to port the existing
> algorithm to do so.

I have implemented quicksort several time on several platforms. But most
times I had old environments like REXX or C.

> http://en.wikipedia.org/wiki/Quicksort
> http://en.wikipedia.org/wiki/Heapsort
>
> Those are two of the best general-purpose sorts, both of which can be
> implemented to be both memory- and time-efficient.

I know.


Marcel

[Arne Vajhøj]

On 7/25/2012 1:20 PM, Marcel Müller wrote:
> On 25.07.2012 16:26, Peter Duniho wrote:
>>> Is there a way to sort an IList<T> in place?
>>
>> Sure, as long as it's not a read-only IList<T>. Of course there is.
>>
>> Now, there's nothing in .NET that I know of that will do that. The
>> built-in
>> sort implementations apply to arrays or List<T> instances. But there's
>> nothing stopping you from writing your own.
>
> Oh, that's the point that I wanted to avoid.
> It's unbelievable that business applications that use a modern
> development environment need to ship with their own general purpose sort
> algorithmn, isn't it?.

No.

You don't want to create a sort method that may perform very
poorly depending on the IList implementation.

You want to create a sort method for something where you know
access via index is fast and then developers can convert as
mentioned in original post.

Arne

[Arne Vajhøj]

Java Collections.sort sort List<T> which is the interface
in Java.

But note what they write in the docs:

<quote>
This algorithm offers guaranteed n log(n) performance. This
implementation dumps the specified list into an array, sorts the array,
and iterates over the list resetting each element from the corresponding
position in the array. This avoids the n2 log(n) performance that would
result from attempting to sort a linked list in place.
</quote>

Arne

[Marcel Müller]

On 25.07.2012 19:46, Arne Vajhøj wrote:
> You don't want to create a sort method that may perform very
> poorly depending on the IList implementation.

Hmm, in C++ STL it is best practice not to expose interfaces that cannot
be implemented reasonably fast. Consequently linked lists do not provide
direct access.

Most of the time .NET follows this rule too. I.e. properties (like Item)
should be O(1) or at most O(log(n)). AFAIK there is no .NET container
that implements IList<> with O(n) member access.

Looking back 20 years, I also prefer this rule, since programmers tend
not to look at the performance of each function that they call in a
loop. I had hundreds of sessions where I had to remove code like that
because it was incredibly slow or it used (shared) system resources
excessively.

From that point of view, LINQ is a pain. While I personally like the
expressive syntax, performance problems have become much more common
with LINQ. Entire sub expressions are evaluated over and over
accidentally. LINQ does not fit very well into non-functional languages.
But there are still many advantages too.


Marcel

[Arne Vajhøj]

On 7/25/2012 4:56 PM, Marcel Müller wrote:
> On 25.07.2012 19:46, Arne Vajhøj wrote:
>> You don't want to create a sort method that may perform very
>> poorly depending on the IList implementation.
>
> Hmm, in C++ STL it is best practice not to expose interfaces that cannot
> be implemented reasonably fast. Consequently linked lists do not provide
> direct access.

.NET LinkedList<T> does not implement IList<T>.

> Most of the time .NET follows this rule too. I.e. properties (like Item)
> should be O(1) or at most O(log(n)). AFAIK there is no .NET container
> that implements IList<> with O(n) member access.

I do not even remember anything besides the array backed List<T> that
implements IList<T>.

But I assume that the original poster must have some class in
mind otherwise the problem would not exist.

And the most likely reason for the existence of such a class
must be that for whatever reason array backed it not possible.

> From that point of view, LINQ is a pain. While I personally like the
> expressive syntax, performance problems have become much more common
> with LINQ. Entire sub expressions are evaluated over and over
> accidentally. LINQ does not fit very well into non-functional languages.
> But there are still many advantages too.

Classic tradeoff.

I have noted the effect as well.

But for small data sizes and modern hardware it does not matter.

Arne

[Marcel Müller]

On 25.07.2012 23:25, Arne Vajhøj wrote:
> I do not even remember anything besides the array backed List<T> that
> implements IList<T>.

Hmm, seems you are right. And the implicit conversion from T[] to
IList<T> seems to be some secret too.

> But I assume that the original poster must have some class in
> mind otherwise the problem would not exist.

No, I prefer IList<T> in public interfaces because it offers the
implementer the option to use T[] for long lived or constant size arrays
and List<T> for arrays that are subject to change. Furthermore I can
replace IList<T> with a read-only proxy in debug builds to ensure
constness in some places where anything else would result in hard to
find race-conditions. Of course, not in this case.


Marcel

[Arne Vajhøj]

I would make it readonly in all build for those cases.

Allowing caller code to access the data directly is
breaking encapsulation.

If a sort is needed then the class should have a sort
method that could sort the implementation.

But OK I have no guarantee that the original poster sees
it that way, so I see your point.

Arne

[Peter Duniho]

On Wed, 25 Jul 2012 19:20:38 +0200, Marcel Müller wrote:

> On 25.07.2012 16:26, Peter Duniho wrote:
>>> Is there a way to sort an IList<T> in place?
>>
>> Sure, as long as it's not a read-only IList<T>. Of course there is.
>>
>> Now, there's nothing in .NET that I know of that will do that. The built-in
>> sort implementations apply to arrays or List<T> instances. But there's
>> nothing stopping you from writing your own.
>
> Oh, that's the point that I wanted to avoid.
> It's unbelievable that business applications that use a modern
> development environment need to ship with their own general purpose sort
> algorithmn, isn't it?.

.NET does already include at least two different sorting APIs (not even
counting "order by" in LINQ, and other corner cases).

You have a specific requirement that is more constraining that what .NET
offers. But you haven't explained the requirement, and it's unusual enough
that it's not surprising that you might have to "roll your own". For most
applications, the difference between O(n log n) and O(n (log n + 2)) is
insignificant, especially given how incredibly fast sequential memory
copies are on modern hardware.

I'm not surprised at all that .NET hasn't addressed this narrow business
case. It's a general-purpose framework, not an "end-all, be-all" one.

What, exactly, is wrong with copying your data to a temporary array,
sorting that, and then copying it back to the IList<T> object?

Pete

[Arne Vajhøj]

On 7/25/2012 8:48 PM, Peter Duniho wrote:
> On Wed, 25 Jul 2012 19:20:38 +0200, Marcel Müller wrote:
>> On 25.07.2012 16:26, Peter Duniho wrote:
>>>> Is there a way to sort an IList<T> in place?
>>>
>>> Sure, as long as it's not a read-only IList<T>. Of course there is.
>>>
>>> Now, there's nothing in .NET that I know of that will do that. The built-in
>>> sort implementations apply to arrays or List<T> instances. But there's
>>> nothing stopping you from writing your own.
>>
>> Oh, that's the point that I wanted to avoid.
>> It's unbelievable that business applications that use a modern
>> development environment need to ship with their own general purpose sort
>> algorithmn, isn't it?.
>
> .NET does already include at least two different sorting APIs (not even
> counting "order by" in LINQ, and other corner cases).
>
> You have a specific requirement that is more constraining that what .NET
> offers. But you haven't explained the requirement, and it's unusual enough
> that it's not surprising that you might have to "roll your own". For most
> applications, the difference between O(n log n) and O(n (log n + 2)) is
> insignificant, especially given how incredibly fast sequential memory
> copies are on modern hardware.

Strictly speaking there are no difference between O(n log n)
and O(n (log n + 2)) at all.

Not that it really matters for your argument, which I agree with.

Arne