Sorting algorithm which alternates equal items <p>What would be a good (simple) algorithm/method for this sorting situation:</p> <p>I have an array of items where each item consists of 2 fields: (ID, Timestamp)</p> <p>There are many pairs of items with the same ID's.</p> <p>I want to sort the array such that the items are alternating among ID's as much as possible, starting from the item with the earliest Timestamp.</p> <p>For example, with this input:</p> <p>(1, 15:00)<br> (1, 15:05)<br> (1, 15:10)<br> (2, 15:15)<br> (2, 15:20)<br> (2, 15:25)<br> (3, 15:30)<br> (4, 15:35)<br> (3, 15:40)</p> <p>I would get this output:</p> <p>(1, 15:00)<br> (2, 15:15)<br> (3, 15:30)<br> (4, 15:35)<br> (1, 15:05)<br> (2, 15:20)<br> (3, 15:40)<br> (1, 15:10)<br> (2, 15:25) </p> <p>I'm primarily looking for a algorithm which is conceptually simple, but of course it's nice if it's performant.</p> <p>Right now the best I can think of is something like: </p> <ol> <li>Init/create temporary array T</li> <li>From the array A: Get item X with earliest Timestamp where ID is not in T</li> <li>Add X to result set R, add X.ID to T, pop X from A</li> <li>As long as X exists, repeat step 2-3, otherwise restart at step 1</li> <li>Quit when A is empty</li> </ol>