Re: [boost] [sorting] Taking away quicksort and mergesort

From: Rene Rivera (grafikrobot_at_[hidden])
Date: 2007-03-17 17:39:33

Rene Rivera wrote:
> Sam Schetterer wrote:
>> Would users care if I took quicksort and merge sort out of the library? They
>> are already implemented by the stl.
> 
> Sorry I haven't looked at your lib yet, I plan to this weekend... But 
> perhaps you should compare you quicksort and mergesort implementation to 
> the stl ones to see if there are differences. I ask because I have a 
> quicksort implementation specifically written, not to be faster, but to 
> have tighter complexity bounds.

To illustrate I expanded a perf test I have for sorting to include the 
two std sorts, and the other sort I have "inplace_mergesort". Sorry 
about the wrapping... The interesting case is at the bottom where it 
sorts 512K strings.

--- Start iteration #0, item count = 524288
---
--| struct rsi_tri_part_quicksort_, no-op: class std::vector<int,class 
std::allocator<int> >
--|   total time     2.1250  iterations     10485760  iteration 
0.0000  iterations/second       4.7059 M
--| struct rsi_inplace_mergesort_, no-op: class std::vector<int,class 
std::allocator<int> >
--|   total time     4.6719  iterations     10485760  iteration 
0.0000  iterations/second       2.1405 M
--| struct std_sort_, no-op: class std::vector<int,class 
std::allocator<int> >
--|   total time     0.5938  iterations     10485760  iteration 
0.0000  iterations/second      16.8421 M
--| struct std_stable_sort_, no-op: class std::vector<int,class 
std::allocator<int> >
--|   total time     1.9063  iterations     10485760  iteration 
0.0000  iterations/second       5.2459 M
---
--| struct rsi_tri_part_quicksort_, reverse: class std::vector<int,class 
std::allocator<int> >
--|   total time     2.1563  iterations     10485760  iteration 
0.0000  iterations/second       4.6377 M
--| struct rsi_inplace_mergesort_, reverse: class std::vector<int,class 
std::allocator<int> >
--|   total time     4.5938  iterations     10485760  iteration 
0.0000  iterations/second       2.1769 M
--| struct std_sort_, reverse: class std::vector<int,class 
std::allocator<int> >
--|   total time     0.6563  iterations     10485760  iteration 
0.0000  iterations/second      15.2381 M
--| struct std_stable_sort_, reverse: class std::vector<int,class 
std::allocator<int> >
--|   total time     2.3438  iterations     10485760  iteration 
0.0000  iterations/second       4.2667 M
---
--| struct rsi_tri_part_quicksort_, random: class std::vector<int,class 
std::allocator<int> >
--|   total time     3.3594  iterations     10485760  iteration 
0.0000  iterations/second       2.9767 M
--| struct rsi_inplace_mergesort_, random: class std::vector<int,class 
std::allocator<int> >
--|   total time     5.1250  iterations     10485760  iteration 
0.0000  iterations/second       1.9512 M
--| struct std_sort_, random: class std::vector<int,class 
std::allocator<int> >
--|   total time     1.5625  iterations     10485760  iteration 
0.0000  iterations/second       6.4000 M
--| struct std_stable_sort_, random: class std::vector<int,class 
std::allocator<int> >
--|   total time     2.4688  iterations     10485760  iteration 
0.0000  iterations/second       4.0506 M
---
--| struct rsi_tri_part_quicksort_, blocks of 3 - no-op: class 
std::vector<int,class std::allocator<int> >
--|   total time     2.2031  iterations     10485760  iteration 
0.0000  iterations/second       4.5390 M
--| struct rsi_inplace_mergesort_, blocks of 3 - no-op: class 
std::vector<int,class std::allocator<int> >
--|   total time     4.6094  iterations     10485760  iteration 
0.0000  iterations/second       2.1695 M
--| struct std_sort_, blocks of 3 - no-op: class std::vector<int,class 
std::allocator<int> >
--|   total time     0.5625  iterations     10485760  iteration 
0.0000  iterations/second      17.7778 M
--| struct std_stable_sort_, blocks of 3 - no-op: class 
std::vector<int,class std::allocator<int> >
--|   total time     1.9063  iterations     10485760  iteration 
0.0000  iterations/second       5.2459 M
---
--| struct rsi_tri_part_quicksort_, blocks of 3 - reverse: class 
std::vector<int,class std::allocator<int> >
--|   total time     2.2656  iterations     10485760  iteration 
0.0000  iterations/second       4.4138 M
--| struct rsi_inplace_mergesort_, blocks of 3 - reverse: class 
std::vector<int,class std::allocator<int> >
--|   total time     4.7344  iterations     10485760  iteration 
0.0000  iterations/second       2.1122 M
--| struct std_sort_, blocks of 3 - reverse: class std::vector<int,class 
std::allocator<int> >
--|   total time     0.6719  iterations     10485760  iteration 
0.0000  iterations/second      14.8837 M
--| struct std_stable_sort_, blocks of 3 - reverse: class 
std::vector<int,class std::allocator<int> >
--|   total time     2.2188  iterations     10485760  iteration 
0.0000  iterations/second       4.5070 M
---
--| struct rsi_tri_part_quicksort_, blocks of 3 - random: class 
std::vector<int,class std::allocator<int> >
--|   total time     3.1094  iterations     10485760  iteration 
0.0000  iterations/second       3.2161 M
--| struct rsi_inplace_mergesort_, blocks of 3 - random: class 
std::vector<int,class std::allocator<int> >
--|   total time     5.1563  iterations     10485760  iteration 
0.0000  iterations/second       1.9394 M
--| struct std_sort_, blocks of 3 - random: class std::vector<int,class 
std::allocator<int> >
--|   total time     1.5313  iterations     10485760  iteration 
0.0000  iterations/second       6.5306 M
--| struct std_stable_sort_, blocks of 3 - random: class 
std::vector<int,class std::allocator<int> >
--|   total time     2.5313  iterations     10485760  iteration 
0.0000  iterations/second       3.9506 M
---
--| struct rsi_tri_part_quicksort_, random: class std::vector<class 
std::basic_string<char,struct std::char_traits<char>,class 
std::allocator<char> >,class std::allocator<class 
std::basic_string<char,struct std::char_traits<char>,class 
std::allocator<char> > > >
--|   total time    39.2656  iterations     10485760  iteration 
0.0000  iterations/second     260.7879 K
--| struct rsi_inplace_mergesort_, random: class std::vector<class 
std::basic_string<char,struct std::char_traits<char>,class 
std::allocator<char> >,class std::allocator<class 
std::basic_string<char,struct std::char_traits<char>,class 
std::allocator<char> > > >
--|   total time   340.3269  iterations     10485760  iteration 
0.0000  iterations/second      30.0887 K
--| struct std_sort_, random: class std::vector<class 
std::basic_string<char,struct std::char_traits<char>,class 
std::allocator<char> >,class std::allocator<class 
std::basic_string<char,struct std::char_traits<char>,class 
std::allocator<char> > > >
--|   total time    44.5469  iterations     10485760  iteration 
0.0000  iterations/second     229.8702 K
--| struct std_stable_sort_, random: class std::vector<class 
std::basic_string<char,struct std::char_traits<char>,class 
std::allocator<char> >,class std::allocator<class 
std::basic_string<char,struct std::char_traits<char>,class 
std::allocator<char> > > >
--|   total time    53.4688  iterations     10485760  iteration 
0.0000  iterations/second     191.5137 K
-- 
-- Grafik - Don't Assume Anything
-- Redshift Software, Inc. - http://redshift-software.com
-- rrivera/acm.org - grafik/redshift-software.com
-- 102708583/icq - grafikrobot/aim - grafikrobot/yahoo