Parity of the Number of Swaps of Swap-Based Sorting Algorithms

Question

If I have a permutation of the integers from 0 to n-1, and I want to sort the permutation in ascending order, is it true that no matter what swap-based sorting method is used, the parity of the number of swaps it will take to sort will be the same among all swap-based sorting methods?

For example, consider a swap-based sorting method I have provided below, written in C++:

(NOTE: pos[i] stores the current index (0 based) of element 'i' in the list)

int cnt = 0; // stores the number of operations
  for (int i = 0; i < n; i++) {
    if (pos[i] != i) {
      cnt++;
      int temp = a[i];
      int temp_pos = pos[i];
      swap(a[i], a[pos[i]]);
      pos[i] = i;
      pos[temp] = temp_pos;
    }
  }

Would swap-based sorting algorithms such as the one above all have the same parity of the number of swaps required to sort when compared to other swap-based sorting methods, when performed on the same permutation of integers from 0 to n-1?

Answer 1

Yes it's true. The sketch of the proof goes something like this.

An inversion in a sequence of elements is any pair of elements that are not in proper sorted order: that is, a[i] > a[j] for some i < j. A fully sorted array has zero inversions. Swapping any two elements changes the total count of inversions by an odd number (proof of this is left as an exercise for the reader). Therefore, if the array initially has an odd number of inversions, an odd number of swaps must be performed to sort it; and if it starts with an even number of inversions, it would take an even number of swaps.