creating a generic sort method

Question

I am learning generic types and wanted to create a generic QuickSort method, the problem is classes are not co-variant and code cannot compile. the problem is making the Partition method generic and i have no idea how to do it, any guidance would be appreciated.

public static void Swap<T>(ref T a, ref T b)
    {
        T temp = a;
        a = b;
        b = temp;
    }

    public static int Partition(int[] array, int mid)
    {
        int midPoint = mid,
            upperBound = array.Length - 1,
            lowerBound = 0;
        while (lowerBound != upperBound)
        {
            while (midPoint < upperBound)
            {
                if (array[midPoint] > array[upperBound])
                {
                    Swap<int>(ref array[midPoint], ref array[upperBound]);
                    midPoint = upperBound;
                    break;
                }
                upperBound--;
            }
            while (midPoint > lowerBound)
            {
                if (array[midPoint] < array[lowerBound])
                {
                    Swap<int>(ref array[midPoint], ref array[lowerBound]);
                    midPoint = lowerBound;
                    break;
                }
                lowerBound++;
            }
        }
        return midPoint;
    }

    public static void QuickSort(int[] array,int lower,int upper)
    {
        int mid = Partition(array, (lower + upper) / 2);

        if (upper <= lower)
        {
        }
        else
        {
            QuickSort(array, mid + 1, upper);
            QuickSort(array, lower, mid - 1);
        }
    }

Answer 1

First step is to actually use generics:

void QuickSort<T>(T[] array, ...)

and

int Partition<T>(T[] array, ...)

In Partition remove the generic argument from Swap. It will be inferred by the compiler.

However, for this to work, you need to constrain T to IComparable<T>:

void QuickSort<T>(T[] array, ...) where T : IComparable<T>

and

int Partition<T>(T[] array, ...) where T : IComparable<T>

Finally, you need to replace the "less than" and "greater than" operators with calls to CompareTo:

if(array[midPoint].CompareTo(array[lowerBound]) < 0)

and

if(array[midPoint].CompareTo(array[lowerBound]) > 0)

Answer 2

What you're looking for is to constrain T to any type that implements IComparable<T>

This MSDN article nicely explains generic constrains in C#. Your method declaration will look like this:

public static T Partition<T>(T[] array, int mid)
    where T : IComparable<T>
{
    //code goes here
}

public static void QuickSort<T>(T[] array, int lower, int upper)
    where T : IComparable<T>
{
    //code goes here
}

It might also be helpful to link you to the MSDN article for IComparable<T>. Wherever you'd regularly compare two ints, you would instead call array[midPoint].CompareTo(array[upperBound]) > 0. All the comparison operators are the same if you check the result of CompareTo against 0.

And a small side note, when you call Swap<int>(..., the compiler can infer the type as int and you can simply call it as Swap(....