For the record, I made one small mistake here: for stack-based recursive
implementations, worst case Quicksort is O(n**2) time and O(n) stack. By
comparison, worst case Heapsort is O(n log n) time and O(log n) stack.
Kind regards,
Ben.
On 20/12/17 12:12, Ben Caradoc-Davies wrote:
It looks like this failure might be caused by the Xalan XSLT embedded in
the JVM standard library using Quicksort to sort an array of integers.
Quicksort is a terrible algorithm because its worst-case performance is
O(n**2):
https://en.wikipedia.org/wiki/Quicksort
Some Quicksort implementations can exhibit this behaviour when the input
is already sorted, already reverse-sorted, or all inputs are the same
(first two criteria combined). Recursive implementations will then use
O(n**2) time and stack.
Heapsort is often preferred because its worst-case performance is O(n
log n):
https://en.wikipedia.org/wiki/Heapsort
--
Ben Caradoc-Davies <b...@transient.nz>
Director
Transient Software Limited <https://transient.nz/>
New Zealand
------------------------------------------------------------------------------
Check out the vibrant tech community on one of the world's most
engaging tech sites, Slashdot.org! http://sdm.link/slashdot
_______________________________________________
Geoserver-users mailing list
Please make sure you read the following two resources before posting to this
list:
- Earning your support instead of buying it, but Ian Turton:
http://www.ianturton.com/talks/foss4g.html#/
- The GeoServer user list posting guidelines:
http://geoserver.org/comm/userlist-guidelines.html
If you want to request a feature or an improvement, also see this:
https://github.com/geoserver/geoserver/wiki/Successfully-requesting-and-integrating-new-features-and-improvements-in-GeoServer
Geoserver-users@lists.sourceforge.net
https://lists.sourceforge.net/lists/listinfo/geoserver-users
