I am implementing an application in Haskell and, for sorting, I use the library function
Data.List.sort. However, I was wondering whether this is the fastest sort implementation in the Haskell standard library (perhaps lists are not the best choice for efficient sorting).
My question is: what is the fastest sorting implementation (container type + sort function) provided by the Haskell standard library? Is there some documentation page listing all library sort functions and comparing them wrt performance?
To provide some more context, I am running a benchmark. I have written a simple program in C, Java, Python and Haskell that
- Reads 1000000 strings (lines) from a text file.
- Sorts the strings using a built-in (library) sorting algorithm.
- Writes the sorted list of strings to a file.
For each implementation, I only measure the sorting time (leaving out the time needed for disk IO). Running the benchmark on Ubuntu 12.04, I get
- C (gcc 4.6.3,
char **): 0.890 s
- Java (OpenJDK 64-Bit 1.7.0_09,
java.util.LinkedList<String>): 1.307 s
- Python (Python 2.7.3,
list.sort()): 1.072 s
- Haskell (GHC 7.4.1,
[Data.ByteString.UTF8.ByteString]): 11.864 s
So I wonder if there is another data type / library function in Haskell that can give better performance.