Fix positive integers n and k.
Let A be an array of length n with A[i] an array of length k where every entry is n-i. For example, with n=5 and k=1, this is just
[ [5] , [4] , [3] , [2] , [1] ]
and for n=5 and k=2, this is
[ [5,5] , [4,4] , [3,3] , [2,2] , [1,1] ]
The goal is to bubble sort this array of arrays by swapping numbers in adjacent arrays (e.g. swap A[i][j1] with A[i+1][j2]) until every entry of A[i] is i+1 for every i.
The question is: how many swaps are necessary and what's an optimal algorithm?
NOTE: There are many, many better sorting algorithms to use. However, for this question, I am only interested in applying a bubble sort as described above. I can only interchange entries from adjacent arrays, and I am only interested in the minimum number of such interchanges necessary. I do appreciate all the suggestions for other sorting algorithms, but this is the problem that I am trying to understand.
EXAMPLES:
For k=1, this is well known. The number of swaps is the inversion number of A regarded as a permutation, and so the minimum number of swaps is the binomial coefficient (n choose 2) = n(n-1)/2 and this can be attained by swapping any out of order pair: A[i] > A[j]. For the first example, here's an optimal bubble sort:
[ [5] , [4] , [3] , [2] , [1] ]
[ [4] , [5] , [3] , [2] , [1] ]
[ [4] , [5] , [2] , [3] , [1] ]
[ [4] , [2] , [5] , [3] , [1] ]
[ [4] , [2] , [5] , [1] , [3] ]
[ [4] , [2] , [1] , [5] , [3] ]
[ [4] , [1] , [2] , [5] , [3] ]
[ [1] , [4] , [2] , [5] , [3] ]
[ [1] , [4] , [2] , [3] , [5] ]
[ [1] ,