Here's the algorithm I had in mind:
First, if the total number of songs is even, no one artist can have more than half of the songs. If the total number of songs is odd, then no one artist can have more than one-half-plus-one of the songs. This is because is if all you have is one other artist, you're going to do an every-other solution and you need to have enough of the other artist to fit between all the original artist's entries.
Now, imagine a gigantic chessboard with as many squares as you need in both directions. Going down the left-hand column, enter the titles for the artist that has the most songs on the squares. Thus, the last song of the most common artist is on the nth square of the leftmost column.
Now, go back to the top, but move one column over. Take the next most numerous artist and start entering its entries on the squares going down the second column. If you run out of entries before reaching the nth square in the second column, take the next most numerous artist and keep going until you reach the nth square of the second column. At that point, go back to the top and continue entering down the third column.
Keep doing this until you run out of songs to enter. To get your sorted list, simply start at the very first square (uppermost left) and read across the rows.
We know this will work because the most numerous artist has, at most half-plus-one songs. Thus, the second column has at most n items, none of which are the first artist and at least n-1 items, meaning that every row has at least two entries except the very last one and thus the final transversal will always have at least one entry that isn't the first artist before wrapping around.
This recurses for all the other columns. Even though we may "wrap around" the bottom of one column to start at the top of the next, we will never catch up to have two entries by the same artist side-by-side horizontally because each artist has fewer than n songs and the column length is n.
And since there is guaranteed a second column and no row has the same artist side-by-side, transversing the grid horizontally will guarantee that you never hit the same artist twice in a row.
Now, there is an improvement one could make to this algorithm if one were programming it. Does it really matter that other than the choice of the most numerous artist for the first column that we choose the rest of the artists in descending order of size? No. Since all of the remaining artists are no larger than the most numerous, we can put them into the grid in any order once we have chosen the most numerous in order to set the column size to that cardinality. We never have to worry about overlap from column to column.
------------------
Rrhain
WWJD? JWRTFM!
™ Version 4.2