Search All of the Math Forum:
Views expressed in these public forums are not endorsed by
NCTM or The Math Forum.


Math Forum
»
Discussions
»
sci.math.*
»
sci.math
Notice: We are no longer accepting new posts, but the forums will continue to be readable.
Topic:
Just finished the fastest ever, general purpose sorting algorithm.
Replies:
29
Last Post:
Jan 8, 2013 10:21 PM




Re: Just finished the fastest ever, general purpose sorting algorithm.
Posted:
Jan 5, 2013 12:39 PM


http://stackoverflow.com/questions/3074861/binarysortalgorithmi
Algorithmi? That's sorta correct. it points to:
http://www.brpreiss.com/books/opus5/html/page487.html
It says: Whereas a linear search requires O(n) comparisons in the worst case, a binary search only requires comparisons
and gives this caveat: The number of comparisons required by the straight insertion sort is in the worst case as well as on average. Therefore on average, the binary insertion sort uses fewer comparisons than straight insertion sort. On the other hand, the previous section shows that in the best case the running time for straight insertion is O(n). Since the binary insertion sort method always does the binary search, its best case running time is . Table summarizes the asymptotic running times for the two insertion sorts.
(sorry that didn't all copy. quicksort is probably better in most cases.)



