Re: [stella] Y-Sorting alternative for Thomas :-)

Subject: Re: [stella] Y-Sorting alternative for Thomas :-)
From: Thomas Jentzsch <tjentzsch@xxxxxx>
Date: Sun, 24 Mar 2002 23:54:46 +0100
Manuel Polik wrote:
>Here's how I sort the sprites in my intelligent flicker 
>routine. It is adopted from Steve Judds and Pasi Ojalas 
>excellent sorting article in C= Hacking #18.
>Might this be even quicker than bubble-sort? :-)

As always: It depends. :-)

This tree-sorting is WAY faster than bubble-sort for large and 
UNsorted lists: O(n log n) vs O(n^2)

BUT, in my (and your?) case, the list is not unsorted, but 
imperfect sorted. From frame to frame, the elements move only 
slightly (e.g. +/-1), so 4,5,6,7,8 might become 5,4,5,8,7 or 
3,6,5,6,9 etc. With bubble-sort, this is corrected very soon 
AND the algorithm can recognize perfect sorting (no swaps) and 
then stop very early. And bubble-sort saves memory, because you 
don't need the link-table.

>Accessing data is way cool, too, this iterates once 
>through the sorted(!) list:

Iterating through a sorted list without the additional table is 
even faster. That helps inside a tight kernel.

Have fun!	

Archives (includes files) at
Unsub & more at

Current Thread