I am going to show you a sorting algorithm. In this example there are 9 letters, three each of A, B and C. They begin in a collated order: ABCABCABC, but they must end in a sorted order: AAABBBCCC in as few steps as possible. A ‘step’ involves selecting some portion of the string and reversing the order of the letters within it.

For our example this is possible in only three steps:

A[BCABCA]BC > A[ACBACB]BC

AA[CBA]CBBC > AA[ABC]CBBC

AAAB[CCBB]C > AAAB[BBCC]C

Now to the actual puzzle. This time you have 12 letters, which start collated and must finish sorted. I will let you decide how many different letters there are in the 12: either 2 each of 6 different letters, 3 each of 4 different letters, 4 each of 3 different letters, or 6 each of 2 different letters. Which of the following collated strings will take the fewest steps to sort?

ABCDEFABCDEF

ABCDABCDABCD

ABCABCABCABC

ABABABABABAB