Quicksort async vs serial

I am playing with async and I figured I'd write a parallel implementation of Quicksort while trying to look at various optimizations. I want to keep the generics (and the overhead of the virtual calls going on here). Other than that I am looking for optimizations that can be made.

```
class Program
{
static int[] initial; //generating random array only once and using copies of it later
private static void Main(string[] args)
{
initial = Enumerable.Range(0, 100000000).ToArray();
Shuffle();
TestLength>(5);
TestLength>(10);
TestLength>(100);
TestLength>(1000);
TestLength>(10000);
TestLength>(100000);
TestLength>(1000000);
TestLength>(10000000);

//oom when trying this one for me
//TestLength>(100000000);
Console.ReadKey();
}

private static void Shuffle()
{
//simple Fisher-Yates shuffle
var random = new Random();
for (int i = initial.Length - 1; i > 0; i--)
{
int j = random.Next(i);
int value = initial[i];
initial[i] = initial[j];
initial[j] = value;
}
}

private static void TestLength(int length) where T:ISortAlgorithm,new()
{
int[] arr = new int[length];
Array.Copy(initial, arr, length);

int[] arr2 = new int[length];
Array.Copy(initial, arr2, length);

Console.WriteLine("Length: " + length);

var timer = new Stopwatch();
var algorithm = new T { Elements = arr };
timer.Start();
algorithm.SortAsync().GetAwaiter().GetResult();
timer.Stop();

Console.WriteLine("Elapsed async: " + timer.Elapsed);

timer.Reset();
algorithm = new T { Elements = arr };
timer.Start();
algorithm.Sort();
timer.Stop();
Console.WriteLine("Elapsed: " + timer.Elapsed);
Console.WriteLine();
}
}

public interface ISort

Your first mistake is to do something with async that is CPU bound. That is not what you use async code for, async code is good for IO bound work, not CPU bound work.

That you have to use Task.Yield() is indeed a indication you are using async code wrong. You should probably switch to the TPL library, and call something like Parallel.Invoke(() => SortAsync(low, store, depth + 1), () => SortAsync(store + 1, high, depth + 1));

(Edit: Parallel.Invoke is actually slightly slower above 100000+ elements, but more reliable and faster below. You should probably tweak the threshold to switch to normal sort in that case, like this).

Your numthreads variable looks more like a numTasks counter.

In your TestLength method, you do not use arr2, i think you meant to use arr2 for the second sort pass, myself i would copy the line Array.Copy(initial, arr, length); after the Console.WriteLine so you can reuse arr

StackExchange Code Review Q#82282, answer score: 7