sort comparison

[Yinfan Li]

Hi,
I don't think I can implement an efficient merge sort, at least not for short time.
I use GNU libstdc++ sort, i.e. sort function in <algorithm> library for comparison. I'm not very sure it's O(m lg m) sort, because it is so optimized that it's not easy to see its complexity.
the result is as follow:
n       m       heap    sort
1024    10240   4299    3022
2048    22528   12513   7860
4096    49152   34737   20389
8192    106496  56907   26860
16384   229376  204123  81440
32768   491520  595794  241229

the first column is n, second m, third running time for heap sort, Professor Turner's version, and forth column sort in GNU libstdc++.

For those who want to see what's going on under libstdc++ sort, here is the link:

sort's definiation: http://gcc.gnu.org/onlinedocs/libstdc++/latest-doxygen/a01494_source.html#l05499

and my testing code is attached.

[Turner Jonathan]

According to the description here

http://www.cplusplus.com/reference/algorithm/sort/

This uses quicksort and is Omega(n^2) in worst-case.
I don't see a mergesort in the standard library.

Jon

> --
> You received this message because you are subscribed to the Google Groups "algolib" group.
> To post to this group, send email to alg...@googlegroups.com.
> To unsubscribe from this group, send email to algolib+u...@googlegroups.com.
> For more options, visit this group at http://groups.google.com/group/algolib?hl=en.
> <sorttest.cpp>

[Yinfan Li]

I google a little bit and find out it's likely that sort in gnu libstdc++ is O(n lg n) for both average and worst case.

"
http://www.sgi.com/tech/stl/sort.html
(N log(N)) comparisons (both average and worst-case), where N is last - first.

Earlier versions of sort used the quicksort algorithm (C. A. R. Hoare, Comp. J. 5, 1962), using a pivot chosen by median of three (R. C. Singleton, CACM 12, 1969). Quicksort has O(N log(N)) average complexity, but quadratic worst-case complexity. See section 5.2.2 of Knuth for a discussion. (D. E. Knuth, The Art of Computer Programming. Volume 3: Sorting and Searching. Addison-Wesley, 1975.) The current implementation of sort, however, uses the introsort algorithm (D. R. Musser, "Introspective Sorting and Selection Algorithms", Software Practice and Experience 27(8):983, 1997.) whose worst case complexity is O(N log(N)). Introsort is very similar to median-of-three quicksort, and is at least as fast as quicksort on average.
"

and gnu libstdc++ might be based on sci implementation, not sure, but it indeed use introsort.

[Turner Jonathan]

Interesting. I've never looked closely at introsort, but the Wikipedia
page describing it says that it's essentially quicksort, but reverts
to heapsort if the recursion depth gets too high. Not sure exactly how
the two are combined, but apparently it uses heapsort
as a "backstop" for the bad-cases that can arise with quicksort.

Jon

[Yong Fu]

Code from stl_algo.h

/// This is a helper function for the sort routine.
02243 template<typename _RandomAccessIterator, typename _Size>
02244 void
02245 __introsort_loop(_RandomAccessIterator __first,
02246 _RandomAccessIterator __last,
02247 _Size __depth_limit)
02248 {
02249 typedef typename iterator_traits<_RandomAccessIterator>::value_type
02250 _ValueType;
02251
02252 while (__last - __first > int(_S_threshold))
02253 {
02254 if (__depth_limit == 0)
02255 {
02256 _GLIBCXX_STD_P::partial_sort(__first, __last, __last);
02257 return;
02258 }
02259 --__depth_limit;
02260 _RandomAccessIterator __cut =
02261 std::__unguarded_partition(__first, __last,
02262 _ValueType(std::__median(*__first,
02263 *(__first
02264 + (__last
02265 - __first)
02266 / 2),
02267 *(__last
02268 - 1))));
02269 std::__introsort_loop(__cut, __last, __depth_limit);
02270 __last = __cut;
02271 }
02272 }
02273

Yong

[Turner Jonathan]

I find this code pretty hideous, but it appears that it just
attempts a quick sort and if the recursion depth exceeds a limit,
it just gives up and does heapsort.

Jon

[Yinfan Li]

So I think we might want to use STL sort, instead of a simple heap sort.
According to David R Musser 1997 paper, ftp://grmanet.sogang.ac.kr/pub/ihm/cs081/08/IntrospectiveSort.pdf,
"for almost all randomly chosen integer sequences introsort is faster than heapsort by a factor of between 2 and 5."
and still have worst case complexity O(m lg m).
I also checked microsoft implementation, and sort is implemented similarly. (because it's template function so I can see the code).