mergesort & quicksort

I've done some comparison between different sort algorithms, and almost nothing beats the build int Arrays.sort, which is a quicksort. And that algorithm is built to well handle nearly sorted sets of data too, which otherwise normally is a problem for quicksort. I would guess that might be a problem in your case.

A major problem in java is the memory allocation and garbagecollection, and quicksort is in-memory, which is a major reason to use quicksort. Mergesort is not in memory, but it can be programmed smartly to not allocate that much extra memory. I would recomend quicksort though, especially the built in one in Arrays.sort.

If you plan to do it yourself, quicksort is not good for nearly sorted arrays/sets.

If you have a sorted set of items that changes order only slightly for each iteration, which might be the case for moving 3d polygons, a smarter algorithm can be used, some sort of bubble sort, where you only switch wrongly placed items (iteration for the moves could be done in logarithmic fashion). This will also be in memory.

Gil

gilroittoa at 2007-7-14 20:31:08 >