Runtime: Implement public partial sort Array API

[iSazonov]

Rationale

• In PowerShell repo we have Sort-Object cmdlet enhanced with -Top and -Bottom parameters - their implementation is based on partial sorting.
  
  
  
  • Currently Linq uses Array.Sort but own internal (not public API) implementation of PartialQuickSort.
  
  
• It seems this is a very popular scenario for web interface to show sorted result by pages. Users use only top items and rarely go to the following pages.

Proposed API

```c#
public abstract partial class Array : System.Collections.ICollection, System.Collections.IEnumerable, System.Collections.IList, System.Collections.IStructuralComparable, System.Collections.IStructuralEquatable, System.ICloneable
{
public static void SortPartial(array array, int index, int length) { }
public static void SortPartial(array keys, array items, int index, int length) { }
public static void SortPartial(array array, int index, int length, System.Collections.IComparer comparer) { }
public static void SortPartial(array keys, array items, int index, int length, System.Collections.IComparer comparer) { }
public static void SortPartialT { }
public static void SortPartialTKey, TValue { }
public static void SortPartialT { }
public static void SortPartialTKey, TValue { }
}

public partial class List : System.Collections.Generic.ICollection, System.Collections.Generic.IEnumerable, System.Collections.Generic.IList, System.Collections.Generic.IReadOnlyCollection, System.Collections.Generic.IReadOnlyList, System.Collections.ICollection, System.Collections.IEnumerable, System.Collections.IList
{
public void SortPartial(int index, int count, System.Collections.Generic.IComparer comparer) { }
}
```

Useful links

https://en.wikipedia.org/wiki/Partial_sorting
https://blogs.msdn.microsoft.com/devdev/2006/01/18/efficient-selection-and-partial-sorting-based-on-quicksort/

Updates

1. Replace startIndex and endIndex with index and length.
2. Add class names.

[iSazonov]

The initial implementation could be the use of PartialQuickSort from Linq.
Ideally I guess it would enhance private void IntrospectiveSort from Array.

[JonHanna]

It seems this is a very popular scenario for web interface to show sorted result by pages.

That's certainly where I got the idea of doing that partial quicksort from.

I'd prefer there was a yay or a nay on dotnet/runtime#24131 before exposing a partial sort, since they yay or nay should carry through to anything like this.

An in-place sort could perhaps benefit from setting the range to sort within as well as the range to get sorted, especially if using it incrementally. Say I have 100 items and I want the get 10 according to some order. If I then want the second "page" I ideally don't want to sort to obtain items 10-19 from items 0-99, but items 10-19 from items 10-99; knowing that items 0-9 are already "below" the first item I'd want. This also stops the algorithm from moving things around in the already-sorted area and then giving up before they are back where they should be (since the whole gain of partial quick sort is that it gives up on chunks it knows it doesn't need to concern itself about). Note that Sort already allows one to set the range the sort happens within.

In terms of down-sides the only negative (as opposed to the all-features-start-out-unimplemented default negative) I can think of is the potential for confusion of already-sorted areas being unsorted by later partial sorts. We'd want to either rule that out in the implementation or make sure it was documented. Again, being able to set the range the sort happens within would mitigate this.

I think I prefer length to endIndex, it avoids confusion about whether endIndex is inclusive or exclusive (there are programming backgrounds that would strongly expect inclusive and programming backgrounds that would strongly expect exclusive, so each is strange to a some group of potential users) and is more inline with many Array methods such as Copy, BinarySearch and indeed, Sort.

[iSazonov]

@JonHanna Thanks for your feedback!
I think honest paging can only be for immutable arrays. So I don't know full right solution. My initial thoughts was about PowerShell scenario to get only N-top (-bottom) elements and web scenario to get first (ex.) 60 elements and show it by 20 elements (expecting 3-sigma rule - nobody use 4th page in Google).
I agree with endIndex to length.

[jkotas]

All new APIs like these should work on Spans, not arrays.

[karelz]

Do I understand it correctly, that the ask is to be able to sort just a specific segment of array?
In that case, adding Sort on Span would be the right thing to do as @jkotas pointed out.

[iSazonov]

No, partial sort does sort _entire array_ but return requested top/bottom (or a range in common case) elements only - the performance gain is that there is no need to sort the tail.
As opposed to this, Array.Sort already implement sorting a specific segment of array.
c# a = 8,5,7,4,1,3,9,6,0,2; Array.SortPartial(a, 5, 6) return 5,6 w/o sorting rest elements.

[karelz]

Ah, ok, that's what I originally thought, but the arg names startIndex and endIndex lead me to believe otherwise. Maybe we could use better names?
What is the keys/items for? Sorting dictionary?

[iSazonov]

startIndex and endIndex came from PartialQuickSort. Partial sort is a generalization of sorting and perhaps these names make sense. Although as suggested above we could use index and length.
The keys/items is from Array.Sort API. I don't know about dictionary sorting. We can see sample in docs

[iSazonov]

I think @jkotas meant https://github.com/dotnet/corefx/issues/15329. It is another proposal and it is currently being implemented by @nietras.
If the proposal were approved, we could ask him to implement it also.

[nietras]

I am indeed currently implementing sorting for spans. As I understand this proposal, it sounds like some kind of partioning like std::nth_element i.e. partition so 0-9 are less than elements in 10-99, followed by a full sort on elements 0-9. One can the continue by partitioning 10-19 and 20-99, sort 10-19 etc.

Thus, this could be implemented by adding an equivalent function to std:nth_element. Not sure what a proper name for that would be in .NET Partition seems apt. I could try to make a proposal for that once I am done with sorting, if there is interest in this.

[JonHanna]

@nietras nth_element is a partitioning selection operation and hence uses a partitioning selection algorithm (generally introselect to avoid the worst-case of quickselect) there are partial sort algorithms that more directly do that operation.

[nietras]

nth_element is a partitioning selection operation and hence uses a partitioning selection algorithm ... there are partial sort algorithms that more directly do that operation.

@JonHanna you are right, of course, it wasn't the best example since it is not exactly what I was proposing either. It isn't std::partition either so perhaps the name Partition is not ideal either... instead it is in fact std::partial_sort (not sure why I forgot that 😦) that could be used as a blueprint for similar functionality in C# i.e. something like:

public static class MemoryExtensions
{
    public static void PartialSort<T>(this Span<T> items, int middle) 
        where T : IComparable<T>;
    public static void PartialSort<T, TComparer>(this Span<T> items, int middle, TComparer comparer)
        where TComparer : IComparer<T>;
    // Convenience overload
    public static void PartialSort<T>(this Span<T> items, int middle, Comparison<T> comparison);
}

PartialSort rearranges elements such that the range [0, middle) contains the sorted middle smallest elements in the range [0, items.Length). The order of equal elements is not guaranteed to be preserved. The order of the remaining elements in the range [middle, items.Length) is unspecified. (modified from http://en.cppreference.com/w/cpp/algorithm/partial_sort)

This can be used with any type of memory, allows inlineable value type comparers. Note this would be restricted to T being IComparable<T> which is a bit different that my proposed Sort API, I want to revisit this for Sort too since this has some down sides... they should be identical in signature though for consistency.

[ericstj]

Now that we have Span.Sort is this proposal still interesting?
https://github.com/dotnet/runtime/blob/f0ede2b86b0f1b86744aa1e020ba1df3ac3d2744/src/libraries/System.Memory/ref/System.Memory.cs#L87-L92

I think it addresses the original scenario.

[iSazonov]

Now this proposal is interesting if we want modernize the old Array type.

[KalleOlaviNiemitalo]

I don't see how the MemoryExtensions.Sort methods address the original scenario. Those methods fully sort the span given, so they are not efficient for partial sort tasks like "what are the five largest of these 100000 integers?"

In C++, std::partial_sort sorts the smallest middle - first elements to the start of the range. @iSazonov's proposed API looks more capable, as it takes both int index and int length parameters, allowing it to sort the largest elements to the end of the array, or median elements to the middle of the array. However, I don't think the current parameter sets of the PowerShell Sort-Object cmdlet would benefit from that capability.

If that capability is not needed, then partial sorts of Span could have these signatures:

 public static partial class MemoryExtensions
 {
     public static void Sort<T>(this System.Span<T> span) { }
     public static void Sort<T, TComparer>(this System.Span<T> span, TComparer comparer) where TComparer : System.Collections.Generic.IComparer<T>? { }
     public static void Sort<T>(this System.Span<T> span, System.Comparison<T> comparison) { }
     public static void Sort<TKey, TValue>(this System.Span<TKey> keys, System.Span<TValue> items) { }
     public static void Sort<TKey, TValue, TComparer>(this System.Span<TKey> keys, System.Span<TValue> items, TComparer comparer) where TComparer : System.Collections.Generic.IComparer<TKey>? { }
     public static void Sort<TKey, TValue>(this System.Span<TKey> keys, System.Span<TValue> items, System.Comparison<TKey> comparison) { }
+    public static void PartialSort<T>(this System.Span<T> span, int count) { }
+    public static void PartialSort<T, TComparer>(this System.Span<T> span, int count, TComparer comparer) where TComparer : System.Collections.Generic.IComparer<T>? { }
+    public static void PartialSort<T>(this System.Span<T> span, int count, System.Comparison<T> comparison) { }
+    public static void PartialSort<TKey, TValue>(this System.Span<TKey> keys, System.Span<TValue> items, int count) { }
+    public static void PartialSort<TKey, TValue, TComparer>(this System.Span<TKey> keys, System.Span<TValue> items, int count, TComparer comparer) where TComparer : System.Collections.Generic.IComparer<TKey>? { }
+    public static void PartialSort<TKey, TValue>(this System.Span<TKey> keys, System.Span<TValue> items, int count, System.Comparison<TKey> comparison) { }
 }

i.e. copy each overload of Sort to PartialSort and add int count after the Span parameters. These would throw ArgumentOutOfRangeException if count < 0 or count > span.Length. After PartialSort returns:

• span.Slice(0, count) contains the count smallest original elements of span in ascending order.
• span.Slice(count) contains the other original elements of span in unspecified order.

If a caller instead wants span.Slice(0, count) to be the count largest elements, it can provide a reverse comparer.

If a caller instead wants span.Slice(span.Length - count) to be the count smallest elements, it can swap them after PartialSort has returned.

Pretty much as in an earlier comment.

[ericstj]

I see. I misunderstood partial sort. This makes a lot more sense and I see the value. Let’s keep it open and continue discussion in 6.0.