Bubble Sort Race Method Analysis of Worst Case Initial Arrangement on 10 tracks: Initial: x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x 1 2 3 4 5 6 7 8 9 ============== After 1 heat per car: x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x 1 x x 4 x x 7 x x x 2 3 x 5 6 x 8 9 ============== After 2 heats per car: x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x 1 x x 4 x x 7 x x x 2 x x 5 x x 8 x x x 3 x x 6 x x 9 ============== ... ============== After 9 heats per car: 1 x x 4 x x 7 x x x 2 x x 5 x x 8 x x x 3 x x 6 x x 9 x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x ============== After 10 heats per car: 1 2 x 4 5 x 7 8 x x x 3 x x 6 x x 9 x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x ============== After 11 heats per car: 1 2 3 4 5 6 7 8 9 x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x ============== After 12 heats per car: 1 2 x 4 5 x 7 8 x x x 3 x x 6 x x 9 x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x ============== After 13 heats per car: 1 2 3 4 5 6 7 8 9 x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x ==============