Inversions in \(k\)-sorted permutations (Q1270771)

From author's abstract: When a list of size \(n\) is nearly sorted, a straight insertion sort algorithm is highly efficient since only a number of comparisons equal to the number of inversions in the original list, plus at most \(n - 1\), is required. We use a definition of nearly sorted, \(k\)-sorted, as given in \textit{K. A. Berman} and \textit{J. L. Paul} [Fundamentals of sequential and parallel algorithms (1997)] and determine the maximum number of inversions in \(k\)-sorted permutations of size \(n\). This number is approximately \(0.6kn\).