Problem

Given n and an array of n integers. Sort the array in ascending order.

Solutions

• Most sorting algorithms are available on wikipedia

Benchmarking

For O(n^2) algorithms

Benchmarking is done for n = 100K. Time measured in seconds.

On my desktop

Algorithm	C++	Lua	Haskell
ShellSort	11	6.45
InsertionSort	9	8.2
SelectionSort	13	5
BubbleSort	44	55

On my laptop

Algorithm	C++	Lua	Haskell
ShellSort	23	6.45
InsertionSort	20	8.2
SelectionSort	26	5
BubbleSort	58	55

For O(nlogn) or better algorithms

Benchmarking is done for n = 10M. Time measured in seconds.

On my desktop

Algorithm	C++	Lua	Haskell
Builtin	5.2	17
QuickSort	5	14
MergeSort	5.5	45
RadixSort	9.7	23
HeapSort	11.4	55

On my laptop

Algorithm	C++	Lua	Haskell
Builtin	15	17
QuickSort	13	14
MergeSort	14	45
RadixSort	25	23
HeapSort	27	55

Remarks

Todo

• How did Lua outperform C++ in small input sizes? Are the C++ versions not optimized enough?