Insertion sort with pairs of numbers already in order
Insertion Sort is one of the algorithms which only swaps adjacent elements if they are out of order. Therefore, it's performance is intimately tied to the number of inversions in the input; see e.g. here for a detailed explanation.

Observe that in your class of inputs, the maximum number of inversions is not $n(n-1)$ as in the unrestricted case, but one less for each pair of elements. Since there are on average $\Theta(n^2)$ many inversions in random permutations, you'll have as many in your ordered-pairs permutations, assuming uniform randomness, because you lose at most linearly many in each.

For the details, find an analysis of Insertion Sort that rests on the number of inversions (e.g. in a good textbook) and change the numbers; the calculations should mostly remain the same.