sort() on large-size non-power of 2 vectors will hang for long periods

[charlw]

When calling sort against large vectors with sizes that are not power of 2, sequential_sort()s will hang for significantly long periods (1000 seconds+) e.g.

const long vecSize = 1048577; // non-power of 2, (2^20)+1
std::vector<float> vecFloat(vecSize);
std::generate(vecFloat.begin(), vecFloat.end(), std::rand);

cl::sycl::queue deviceQueue;
sycl::sycl_execution_policy<class Sort> sortPolicy(deviceQueue);
std::experimental::parallel::sort(sortPolicy, vecFloat.begin(), vecFloat.end());

Comparing time vs. std::sort() with std::chrono::steady_clock::now(); produced the following:

// 1048576 (2^20), bitonic_sort
std time: 288
ParallelSTL time: 131

// 1048577 (2^20) + 1, sequential_sort
std time: 289
ParallelSTL time: 1346030

This issue begins to occur once vectors reach the size 10,000-100,000 range, and occurs consistently after that. It does not seem to be limited to specific targets, persisting across intel:cpu, intel:gpu etc.

[charlw]

Spoke to @AdamHarries about this last week - the long sort time is due to sequential_sort being implemented as n^2.

I've tried a number of common sort algorithms this week, many of which were thrown out (sort time >1 minute, invalid results etc.). Out of the ones tried, merge sort came out the quickest:

// 1048577 (2^20) + 1, original sequential_sort
std time: 289
ParallelSTL time: 1346030

// 1048577 (2^20) + 1, merge sort:
std time: 289
ParallelSTL time: 150

For very large N like in this case, ParallelSTL will outperform std::sort(). However, std::sort tends to outperform this implementation at smaller size vectors.

I've created a PR for the merge sort implementation here.