The model of the sorting problem is as follows. Assume array is the array of numbers to be sorted. The sorted array is represented by a permutation of the original array. Given N numbers to sort, a permutation array perm of size N is set up with each variable in this array having domain 0..N-1. So, for instance, element i in the permuted array corresponds to the original array element perm[i]. The goal is to produce a perm array where, for all i in 0..n-2: array[perm[i]] <= array[perm[i + 1]], that is, the ordered array is non-decreasing.

To use local search to find the sorted array, we need an appropriate cost function. A cost function which results in a simple search space associates a cost of 0 or 1 with each pair of values in the array to be sorted. The cost is 0 if they are in the correct order (lower before higher, or both values equal), and 1 if they are not. By reducing this cost to zero, the array can be sorted. This cost function also has the other desirable feature that when any pair of elements are swapped from an incorrect order to a correct order, the cost is reduced. This allows us to use a simple greedy improvement scheme to find the minimum.