Faster Array Sort [Take 3][updated 2]

Not so long I’ve new test results for sorting methods. Now I decided to get everything I can from Quick sort algorithm. I’ve searched for all fast implementations and try to reuse them for Flash. I’ve learnt that non-recursive method surely would be faster then recursive calls. So now we have several non-recursive implementations one of them run faster on PC another on Mac. Better check yourself and see what it faster for you.


Get Adobe Flash player

[UPDATED]
I’ve add some code optimization tips. And it looks like we got some speed improvements. Specially in Non recursive methods.

[UPDATED 2]
More optimization tips. Added FlashSort algorithm that became the fastest in my tests.

Here is my test results for PC and Mac sorting 100K length array:

———— PC ————

  • Qsort + Insertion Sort | 57 Ms.
  • 3 Way Qsort + Insertion | 52 Ms.
  • Non-recursive Qsort | 53 Ms.
  • Optimized Non-recursive Qsort | 36 Ms.
  • Non-recursive Qsort II | 43 Ms.
  • FlashSort | 29 Ms.
  • Built in Array Sort | 90 Ms.

———— Mac ————

  • Qsort + Insertion Sort | 49 Ms.
  • 3 Way Qsort + Insertion | 50 Ms.
  • Non-recursive Qsort | 49 Ms.
  • Optimized Non-recursive Qsort | 47 Ms.
  • Non-recursive Qsort II | 58 Ms.
  • FlashSort | 33 Ms.
  • Built in Array Sort | 85 Ms.

Download Sorting Test Class

@katopz If u need fast sort of 3D Vectors I would recommend to use 2 Vectors as I wrote before. One containing your projected vertices coordinates (I suppose u use Utils3D.projectVectors) and another Vector. containing indices to Z position of each vertice in projected Vector array. U can see how it works in my first post on Faster Array Sort. I was sorting indices vector acording to values form Vector with real Z positions.