News for hackers. Stuff that matters.

A comment on Potential Quicksort replacement in java.util.Arrays with new Dual-Pivot. Parent comment

Re:Potential Quicksort replacement in java.util.Arrays with ... by GrandMasterBirt on Friday September 11, 2009 @12:15PM (#817594)
Having N > 2 will require you to do a sort on the pivots :P Also you will require that the array size be at least N. N = 2 is a perfect size --

size = 0 -> no sort

size = 1 -> no sort

size = 2 -> pivots can be made, thus can be sorted

etc.

[ Parent | on HN ]
Re:Potential Quicksort replacement in java.util.Arrays with ... by iclelland on Friday September 11, 2009 @12:20PM (#817604)
Having N > 1 requires you to do a sort on the pivots. From the algorithm:

  3. P1 must be less than P2, otherwise they are swapped.
[ Parent | on HN ]
Re:Potential Quicksort replacement in java.util.Arrays with ... by swac on Friday September 11, 2009 @07:48PM (#818356)
If you determine the number of pivots when you write the algorithm, they could be sorted in constant time. It would just require a lot of if-else branching...
[ Parent | on HN ]