Andrei Alexandrescu:

> c) add introspection to the algorithm, i.e. if an attempt to partition hits the worst case or near worst case, just try another pivot instead of moving forward with the sorting stage.

Or switch to a sort that is guaranteed to have a pseudo-linear complexity.
I am not sure, but I think the C++ STL sort does this.


> TimSort is slower on average.

Here it's not easy to define what "average" is. Python devs think that a common case is an array with mostly sorted data with unsorted data at the end.

Bye,
bearophile

And by the way, I still suggest a dual-pivot quicksort:

http://permalink.gmane.org/gmane.comp.java.openjdk.core-libs.devel/2628

Bye,
bearophile

On Friday, 19 April 2013 at 21:03:23 UTC, Ivan Kazmenko wrote:
> Hi!
>
> Consider a sorted array.  Append an element that is less than all the previous elements.  Then sort the array again by the sort function from std.algorithm.
>
> ....
>
> With n = 30_000 as in the example, this takes time of the order of a second on a modern computer, which is clearly O(n^2).  I am using DMD 2.062.

I filed a bug report for this issue a year ago:
http://d.puremagic.com/issues/show_bug.cgi?id=7767

I've been meaning to fix this issue myself. Time allowing, I'll do it soon.

On Saturday, 20 April 2013 at 16:35:25 UTC, Dmitry Olshansky wrote:
> And this all is good but TimSort allocates O(N) memory. The constant in front of N is smallish less then 1.0 but it could cause some grief.

Worst case is O(n/2), but it starts small and doubles in size as needed. On a partially sorted array, it may only use a small amount of memory.

Xinok:

> I've been meaning to fix this issue myself. Time allowing, I'll do it soon.

Good. And if you are willing, please also take a look at the parallel sort problem I've raised:

http://forum.dlang.org/thread/iyunhhsbmurqyouyrhob@forum.dlang.org

Bye,
bearophile

On Tuesday, 23 April 2013 at 01:28:56 UTC, bearophile wrote:
> Xinok:
>
>> I've been meaning to fix this issue myself. Time allowing, I'll do it soon.
>
> Good. And if you are willing, please also take a look at the parallel sort problem I've raised:
>
> http://forum.dlang.org/thread/iyunhhsbmurqyouyrhob@forum.dlang.org
>
> Bye,
> bearophile

I could, but I'm not sure what the general consensus is on std.parallel_algorithm as it's been brought up before in a similar context.

On 4/22/13 5:52 PM, bearophile wrote:
> Andrei Alexandrescu:
>
>> c) add introspection to the algorithm, i.e. if an attempt to partition
>> hits the worst case or near worst case, just try another pivot instead
>> of moving forward with the sorting stage.
>
> Or switch to a sort that is guaranteed to have a pseudo-linear complexity.
> I am not sure, but I think the C++ STL sort does this.

There's not "the C++ STL sort". Any implementation is fine as long as it has O(n log n) expected run time.

>> TimSort is slower on average.
>
> Here it's not easy to define what "average" is. Python devs think that a
> common case is an array with mostly sorted data with unsorted data at
> the end.

Note that in this case it's sorted data followed by its smallest element. (Changing the value does improve sped.) This is hitting a corner case: median of 3 will pick the smallest element, which will lead to an inefficient partition. I haven't looked at the code, but it seems the smallest element again makes it to the beginning and the end of the array so it's again picked etc.

One simple solution to this (which I forgot to mention) is picking a pivot at random.


Andrei

Andrei Alexandrescu:

> There's not "the C++ STL sort". Any implementation is fine as long as it has O(n log n) expected run time.

This seems to use the Introsort:
http://www.sgi.com/tech/stl/sort.html

I don't know if Xinok has tested a 2-pivot quicksort (called by
the usual Introsort setting).

Bye,
bearophile

On Tuesday, 23 April 2013 at 14:12:01 UTC, bearophile wrote:
> Andrei Alexandrescu:
>
>> There's not "the C++ STL sort". Any implementation is fine as long as it has O(n log n) expected run time.
>
> This seems to use the Introsort:
> http://www.sgi.com/tech/stl/sort.html
>
> I don't know if Xinok has tested a 2-pivot quicksort (called by
> the usual Introsort setting).
>
> Bye,
> bearophile

On an average case, two-pivot quick sort will increase the number of comparisons by about 50%, reason being that about half the elements will be greater than the first pivot and have to he compared to the second pivot. There's also a greater complexity given there are three partitions rather than two, increasing the amount of I/O necessary.

Introsort is simply a quick sort which falls back to a heap sort after so many recursions to guarantee O(n log n) performance. I've implemented this using a median of five and it works excellent. This is what I plan to contribute to Phobos.

Choosing a random pivot will always invoke "average" performance where as finding the median of N elements usually achieves better performance on sorted lists. You also have to be careful that equal elements are distributed equally among both partitions, else a list with many elements equal to the pivot will still achieve poor performance. (equal elements would all fall onto one side of the pivot)

On Monday, 22 April 2013 at 21:34:47 UTC, Andrei Alexandrescu wrote:

> a) choose median of five

Sounds like it could decrease speed on average, and still perhaps fail on a simple case like [0, 1, 2, 3, ..., 999, 0, 0] or something?  Didn't test it though.

> b) if the array is large, sort a stride of it first (e.g. 1%) then choose the pivot as the median point of that stride

A bad case would be, e.g., the array containing almost sorted parts, and the stride getting taken from the part where lowest or highest elements reside.

> c) add introspection to the algorithm, i.e. if an attempt to partition hits the worst case or near worst case, just try another pivot instead of moving forward with the sorting stage.

Now, trying another pivot again and again could give the same O(n^2) in a bad case.

> One simple solution to this (which I forgot to mention) is
> picking a pivot at random.

But it would again mean that the sort function depends on global state (RNG state).  And if it doesn't (a local RNG is initialized somehow each time), an adversary would just have to hardcode it once to get the same O(n^2) worst case anytime he wants.

And on Tuesday, 23 April 2013 at 01:10:26 UTC, Xinok wrote:
> I filed a bug report for this issue a year ago:
> http://d.puremagic.com/issues/show_bug.cgi?id=7767
>
> I've been meaning to fix this issue myself. Time allowing, I'll do it soon.

What I wonder now, what would be the goal of such a fix?

One possible goal would be to have an O(n log n) worst case sort.  And that would perhaps cost some speed and/or memory on average.  Besides, such a sort function is already implemented (TimSort), so it's just a matter of setting the default then.

Another goal would be to have O(n^2) only for cases which don't have a reasonable chance to occur in real world, but could still be constructed artificially by an adversary.  And that could perhaps be done by just changing the getPivot implementation.  Other languages' experience may be useful here:

1. GNU C++ 4.x std::sort implementation is IntroSort [1].
2. Microsoft .NET used Quicksort up to version 4.0 [2].
   Now in .NET 4.5 they use Introsort too [3].
3. For primitive types, Java 6 used a tuned QuickSort [4].
   The current Java 7 uses Dual-Pivot QuickSort [5].
   Java uses TimSort for Objects [6].
4. Python uses TimSort since version 2.3 [7].

In any case, there are techniques to construct a bad case given a QuickSort implementation.  One of them is described by M. Douglas McIlroy in "A Killer Adversary for Quicksort" [8].  We run QuickSort on a would-be-array "a" controlling the "a[i] < a[j]" predicate, and, using only certain assumptions (not looking at the code!), we build a killer-case array on the fly.  Given some thought, the technique could perhaps be extended to Dual-Pivot QuickSort too.  As long as some flavor of QuickSort (and topN) is in Phobos, such a unittest would fit the sort implementation nicely, if only to show just how "bad" it can get.

Ivan Kazmenko.

-----

References:
[1] http://gcc.gnu.org/onlinedocs/libstdc++/libstdc++-html-USERS-4.4/a01027.html#g152148508b4a39e15ffbfbc987ab653a
[2] http://msdn.microsoft.com/en-us/library/6tf1f0bc%28v=vs.100%29.aspx
[3] http://msdn.microsoft.com/en-us/library/6tf1f0bc%28v=vs.110%29.aspx
[4] http://docs.oracle.com/javase/6/docs/api/java/util/Arrays.html#sort%28int[]%29
[5] http://docs.oracle.com/javase/7/docs/api/java/util/Arrays.html#sort%28int[]%29
[6] http://docs.oracle.com/javase/7/docs/api/java/util/Arrays.html#sort%28java.lang.Object[]%29
[7] http://en.wikipedia.org/wiki/Timsort
[8] http://www.cs.dartmouth.edu/~doug/mdmspe.pdf