SBBI – Sorting by Block-Interchanges

Say you are given a permutation of the numbers 1,…,n. The problem is to sort the permutation such that the numbers are in ascending order. The only operation you are allowed to perform is a block interchange, that is, you may take two blocks consisting of consecutive elements of the permutation and swap them.

We have implemented two versions of an algorithm proposed by David A. Christie (see references). The first is an interactive version which you may try out directly in your browser. This version has a quadratic runtime.

The second version achieves a runtime of O(n log n) by using a different data structure for the permutation. It is written in C++, can be used from the command line, and it is available for download.