This is a rather specific problem and somewhat contrived. Found on careercup.com.
There is an array of 3-tuple, in the form of (a, 1, 5). The first element in the tuple is the id, the second and third elements are both integers, and the third is always larger than or equal to the second. Assume that the array is sorted based on the second element of the tuple. Write a function that breaks each of the 3-tuple into two 2-tuples like (a, 1) and (a, 5), and sort them according to the integer.
E.g. given (a, 1, 5), (b, 2, 4), (c, 7, 8), output (a, 1), (b, 2), (b, 4), (a, 5), (c, 7), (c, 8).
My strategy was: loop through from beginning to end, break up the tuple if it isn't already, use binary search to find the insertion point of the second half of the tuple, and insert it. I think it's O(nlog n). Unfortunately the insertion of the second tuple could be O(n) due to having to shift over lots of elements potentially.