   Best sorting method for particle systems
  Until now ive just been using stl::sortbut really havent given it much thought, has anyone done any benchmarking with standard particle system usages? eg often from frame to frame the datas gonna be pretty coherent.ta zed   
  I'd have to think this is implementation-specific. If your code uses a lot of memory and you need to use more sparingly, wouldn't you avoid using quick sort (or any heavily recursive functions)? If you desire speed, most of all, wouldn't you WANT to use quick sort?   ;  Isn't insertion sort said to be quite efficient if the data is already almost sorted? (Don't know for sure.)   ;  I always used insertion sort. It doesn't need any more space and as already said particle positions normally don't change much from one frame to another and insertion sort is fast with almost sorted data. As a matter of fact depending on the pivot element of quicksort, quicksort might be much slower with already sorted data (worst case O(n²)).   ;  What are you sorting the particles by? Do you need a comparison sort (generic operator <) or can they be sorted by a single value? If they can be sorted by a float/int, then you should try radix sort ( O(n) instead of O(n*log(n)) of comparison sorts)   ;  If speed is paramount over a large number of particles, you might wanna consider a Radix sort.http://en.wikipedia.org/wiki/Radix_sortThey have the nice property of being O(n) for fixed sized items.*edit: _swx_ beat me to it   ;  You probably shouldn't be doing a full sort of the particles every frame.  Instead, I would perform up to N passes of some bubble sort variant (maybe Shaker sort).  That way you're guaranteed that your particles are more sorted than they were last frame (you can still have frames where they're unsorted, but they'll be less unsorted during the next frame), and you have an upper bound on the amount of time the sort can take in the worst case.[Edited by - Numsgil on September 28, 2008 2:35:27 PM];  nice page with sort routines in javahttp://www.cs.ubc.ca/~harrison/Java/sorting-demo.htmlI'll have a look into radix sort, speedwise it does look the fastest (though memory maybe else but thats less important);  The ideal option for particle systems is of course not to sort them. You can do that if you can get away with additive blending as it doesn't matter which order you add them up in you get the same result. In D3D that would be:SetRenderState(D3DRS_SRCBLEND, D3DBLEND_ONE);SetRenderState(D3DRS_DESTBLEND, D3DBLEND_ONE);SetRenderState(D3DRS_BLENDOPP, D3DBLENDOPP_ADD);If you can do that or not mostly depends on what the particles look like (bright particles on a darker background work best). Note that you want to use black rather than transparent as a background colour if you're blending them like that.   ;  I dont sort particles, or at least havent found the need to in the scope of my small game projects.Turn off depth writes for particles, works for modulative particles also (glBlendFunc(GL_SRC_ALPHA,GL_ONE_MINUS_SRC_ALPHA))   