Extracting Array.Sort behavior to an abstract class to support different types of sorting algorithms

[dckcosta]

Issue

Trying to incorporating a new type of sorting, more efficient in almost sorted array, like TIMSORT (details of the issue - dotnet#2252) and after some initial discussions with coreclr team, we agreed that we need to refactor the current implementation of Array.Sort which doesn’t support the flexibility to use different types of sorting algorithms. We are designing a new implementation (using similar model to solution described by Strategy Design Pattern), which will support the existing IntroSort, and also will allow flexibility to implement other new types of sorting algorithms, including TimSort.

Current Usage

This is how currently the users call the Array.Sort API which internally will use the IntroSort algorithm to sort an array:

// Declaring an Array
string[] array = new string[] { "5", "2", "13", "8", "4", "3", "2", "4", "6" };
IComparer scomparer = new StringComparer();
Array spawn = (Array)(array.Clone());

//This SORT will ALWAYS use Introsort algorithm.
Array.Sort(spawn, index, length, comparer);

Proposed API

This is how the new SORTING abstract class will look like:

public abstract class Sorting<TKey, TValue>
{

   public virtual void Sort(TKey[] array)
    { }
    public virtual void Sort(TKey[] array, int index, int length)
    { }
    public virtual void Sort(TKey[] array, Comparison<TKey> comparison)
    { }
    public virtual void Sort(TKey[] array, int index, int length, System.Collections.Generic.IComparer<TKey> comparer)
    { }
    public virtual void Sort(TKey[] keys, TValue[] items)
    { }
    public virtual void Sort(TKey[] keys, TValue[] items, int index, int length)
    { }
    public virtual void Sort(TKey[] keys, TValue[] items, System.Collections.Generic.IComparer<TKey> comparer)
    { }
    public virtual void Sort(TKey[] keys, TValue[] items, int index, int length, System.Collections.Generic.IComparer<TKey> comparer)
    { }

}

This example of Concrete classes implementation:

public class IntroSorting<TKey, TValue> : Sorting<TKey, TValue>
{
    public override void Sort(TKey[] array, int index, int length, System.Collections.Generic.IComparer<TKey> comparer)
    {
        //It will call the current Array.Sort Implementation; Just a wrap 
        Array.Sort<TKey>(array, index, length, comparer);
    }
    public override void Sort(TKey[] keys, TValue[] items, int index, int length, System.Collections.Generic.IComparer<TKey> comparer)
    {
        //It will call the current Array.Sort Implementation; Just a wrap 
        Array.Sort<TKey,TValue>(keys, items, index, length, comparer);
    }
}

public class TimSorting<Tkey, TValue> : Sorting<Tkey, TValue>
{
    public override void Sort(Tkey[] array, int index, int length, System.Collections.Generic.IComparer<Tkey> comparer)
    {
        //Implementation of TimSort Algorithm
    }
    public override void Sort(Tkey[] keys, TValue[] items, int index, int length, System.Collections.Generic.IComparer<Tkey> comparer)
    {
        //Implementation of TimSort Algorithm
    }
}

New Usage

Declaring an Array

string[] array = new string[] { "5", "2", "13", "8", "4", "3", "2", "4", "6" };
IComparer<string> scomparer = new StringComparer();
Array spawn = (Array)(array.Clone());

//Now the user can use the different types of Sorting. Something like:
TimSort myTimSortAlgorithm = new TimSort();
myTimSortAlgorithm.Sort(spawn, index, length, comparer);

//or
QuickSort myQuickSortAlgorithm = new QuickSort();
myQuickSortAlgorithm.Sort(spawn, index, length, comparer);

Details

A few more details about some decisions we made when designing this API:

1. When designing this new API we considered for quite some time using Interface instead of Abstract class. However, in order 1) to continue to support all the overloaded methods currently available through Array.Sort and 2) don’t force the users, who want to create/extend a new Sorting class, to implement all overloaded methods. With the Abstract class approach the concrete class can delegate the implementation to the base class for some of the methods.
2. We are going to cover only the Generic type methods for the existing Sort.Array in the new API.
3. We decided to go with generic in the class (class Sorting ) instead of the Method (Sort) because if certain new derived sorting class work only for particular types, we don’t have to add special logic in the Sort methods.
4. The initial Sorting algorithm that we want to support (TimSort, IntroSort and Insertion Sort) are in-place are in-place, the SORT methods are going to return VOID and if the user needs to keep the initial state of the array, they will have to clone it before calling SORT method.

Open Questions

Pull Request

Updates