Inversions in k-sorted permutations
Abbreviated Journal Title
Discret Appl. Math.
inversions; permutations; insertion sort; k-ordered; k-sorted; Mathematics, Applied
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 Berman (1997) and determine the maximum number of inversions in k-sorted permutations of size n. This number is approximately 0.6kn. (C) 1998 Elsevier Science B.V. All rights reserved.
Discrete Applied Mathematics
"Inversions in k-sorted permutations" (1998). Faculty Bibliography 1990s. 2229.