Вычисления проводились в 2 потока на машине
Intel Pentium DualCore E2200 (2.2 GHz, 1ГБ ОЗУ)
 (среда разработки MS Visual Studio 2005 Standard, компилятор Intel C++ Compiler 11.0.066)

Эффективность последовательного нерекурсивного алгоритма по отношению к классическому последовательному рекурсивному была проверена на практике:

Число элементов массива N	Ускорение за счёт устранения рекурсии S
10000	1,559985
100000	1,556278
500000	1,456170
1000000	1,559127
5000000	1,504626
10000000	1,538583
50000000	1,544458

Затем была проверена эффективность распараллеленного нерекурсивного алгоритма по отношению к последовательному нерекурсивному:

Число элементов массива N	Теоретическое ускорение S	Практически достигнутое ускорение S
10000	1,86002	0,448188
100000	1,886426	1,498564
500000	1,899657	1,27027
1000000	1,904451	1,280044
5000000	1,913991	1,367422
10000000	1,917538	1,328854
50000000	1,924743	1,463995

Из таблицы видно, что для массивов из 10000-50000 элементов ускорение меньше 1, так как накладные расходы на создание параллельных потоков превышают выгоду от ускорения сортировки. Также практически достигнутое ускорение ниже расчетного, что можно объяснить изначально повышенной эффективностью нерекурсивного алгоритма (сравнение с рекурсивным показывает эффективность порядка 2,2-1,8) и, возможно, вносимыми компилятором дополнительными оптимизациями, приближающими последовательный алгоритм по эффективности к параллельному.