sorting in js

suggestions for sorting algorithm suitable for sorting midi events? for sample accurate communication and handling and automation in a set of plugins i'm working on (speech synth), i need to make sure the incoming midi events (in @block) are sorted by increasing offsets (so that i can handle one by one, and count down a samples_until_next_midi_event variable). after some experimentation, i've seen that if you play realtime midi keys/knobs, and have some other plugins sending midi messages, and also incoming midi from some sequencer items, all at the same time, the midi messages you get with midirecv() aren't always sorted properly by. so, it seems like i need to do the sorting myself... any ideas of what kind of algorithm would work best, considering both cpu use, and the limitations of the js language (pointers, lists, buffers, ..)?

insertion sort 

i'm answering myself here, well, well. anyway... trying to convert something i found here: Code:

Suppose we should make it just qsort() the input... it should really qsort the output anyway, so maybe you should just try putting a js midi passthru and see if that gets it sorted? A good algorithm, since you lack functions for recursion, and since you are doing offsets of integers and limited range, might be a radix sort. -Justin

And don't forget to invert the free radical quantum field permeating the intermavermirator valve. D PS :D

sort-test 

i used this small js-thing for experimentation and checking the midi event offsets.. the (normally black) gfx area flashes red for a moment if the events for the current block is _not_ sorted by offset properly. or, actually, when any of the midi events have an offset which is smaller than any of the previous events in the block.. i have a track playing with an item full of midi notes, and at the same time hammer away on an external midi keyboard, and also, at the same time another track which is sending midi events to this track.. seems like (especially) the realtime midi keyboard events are not sorted in with the rest, but appended to the end of the list of events... so, again, will the midi events be sorted by reaper in the future, will there be a kind of sort_events() function in js, or should i still do the sorting myself for plugins where the order is really important? if not, there could be conflicts, note off coming in before note on, etc... or i could check every single event for every sample or every block i process, which could be quite inefficient in some situations, with lots of events, very-very small note length, etc, ... Code: