Anyone got an efficient array sort function? (for depth sorting sprites)

[rich]

I'm trying to sort an array of sprites based on their y value. The item at the start of the array is drawn first (so at the 'back' of the display list)

 

Lots of sprites will have the same y value, in which case they should not be moved anywhere in the array. For this reason you can't use the native Array.sort (unless there is a compare function I've not yet tested that solves it?) as when items are equal they are shuffled around at will, causing them to constantly flicker as they all swap depths.

 

So.. anyone got some code they could contribute that solves this?

[Sebi]

children.sort(function(a,{  

    if (a.position.y > b.position.y) {

        return 1;

    }

    if (a.position.y < b.position.y) {

        return -1;

    }

    return 0;

});

 

This doesn't work?

 

Same value should stay untouched.

[rich]

Nope, they don't stay untouched. The above was the first thing I tried.

 

From various answers on twitter it seems I need to use some kind of arbitration value.. a sprite ID, timestamp, etc. Pain in the ass.

[Geoff]

I don't have an exact answer for you, but something to look into might be an insertion sort. I've been meaning to try this out because it's supposedly pretty fast for sets that are already mostly sorted and is stable (equal items don't swap).

 

Edit: Our current sorting works like you've mentioned above. We assign IDs to each renderable object upon creation and sub-sort based on that if the depth values are equal:

function (a,  {  return (a.z === b.z) ? (a.id - b.id) : (a.z - b.z);}

[rich]

Thanks Geoff - yeah I've gone through and applied a z-depth value to all objects and now sort against my criteria + that and it works fine.

[green_gron]

You can choose stable sort with better performance than insertion sort O(n²). Almighty wikipedia: Comparison of algorithms

[d13]

sprites.sort(byDepth);

function byDepth(a, {

  if (a.y * a.z < b.y * b.z) {

    return -1;

  } else if (a.y * a.z > b.y * b.z) {

    return 1;

  } else {

    return 0;

  }

}

[Antriel]

You can choose stable sort with better performance than insertion sort O(n²). Almighty wikipedia: Comparison of algorithms

You can hardly find better algo than insertion sort for nearly sorted arrays. Also it always depends on many things and you can't say really until you test it. Looking just at O complexity will not be very precise. Also you will implement insert sort much faster than say heap sort.