Replacement of dual-pivot quicksort in java.util.Arrays with new 3-pivot quicksort?

2017-11-24 Thread David McManamon
Hi, I found the 2009 discussion and work surrounding dual-pivot quicksort fascinating. At that time, 3-pivot quicksort was described as slower; however, since then a new 3-pivot partition algorithm was published and if you want the fastest sorting time for primitives then the results are again ve

AVL tree implemented in the style of TreeMap for better performance

2017-10-18 Thread David McManamon
If the BBST performance numbers from Ben Pfaff's c language research in 2004 https://benpfaff.org/papers/libavl.pdf are correct then it seems the red-black tree implementations that are so popular in the JDK might be worth another look. However, when I surveyed the AVL implementations in the Java