mkqsort

[TimoVJL]

I test sort string pointers with qsort:
Strings from bible.txt.
mkqsort: 106ms
quicksort_str: 193ms
timsort: 235ms
PellesC    qsort: 257ms
msvcrt.dll qsort: 346ms

BTW:
What is best algo for sorting string pointers?

[Snowman]

I don't know what the best algorithm is. However I remember reading somewhere that std::sort() from the C++ standard library is based on Timsort.

Maybe also take a look at Burstsort which, according to Wikipedia, delegates to multikey quicksort (so you don't have to start from scratch).

[jj2007]

I test sort string pointers with qsort:
Strings from bible.txt.
mkqsort: 106ms
quicksort_str: 193ms
timsort: 235ms
PellesC    qsort: 257ms
msvcrt.dll qsort: 346ms

Looks a bit slow. Which cpu? Reading the file included? bible.txt around 4MB, 30,000 lines?

[TimoVJL]

AMD 2.8 GHz.
Possible same bible.txt, not included here, but can be found from here in this zip

Links:
Article here and some tests here

[Grincheux]

Are there the same results with differents compilers?
Perhaphs the algorythm is not very fast but the compiler very good!

[TimoVJL]

With msvc 2015 (19.00) and with -Ox 90 ms lowest value.

EDIT:
Results with random words:
268 ms MSVC 2015
271 ms gcc 4.6.1
279 ms gcc 5.1.0
288 ms PellesC

another word set 10 times AVG:
242 ms msvc 2015
248 ms gcc 3.4.5
260 ms gcc 4.8.1
264 ms gcc 5.1.0
265 ms PellesC 8

TestSort.zip PellesC project
TestSortMS.zip MSVC 19.00 compiled TestSortMS.exe.
test_words.zip test_words.exe for generating tests words.

[jj2007]

Actually, that is pretty fast. I erroneously thought you meant sorting the bible line by line.

[Grincheux]

There are programmers like Timo that write very good algorythms, but I want to ask if Pelle can introduce them in the C library ?

[TimoVJL]

Not mine.
mkqsort is from here, Timo Bingmann

New test set:
237 ms msvc 2015
265 ms PellesC 8
270 ms gcc 5.1.0
279 ms gcc 3.4.5

239 ms msvc 2015 x64
240 ms gcc 5.1.0 x64
256 ms PellesC 8 x64