In computational tasks, dealing with sorting data often requires not just an ordered result but also a mapping back to the original index positions. This functionality is essential when we need to maintain relational data or when changes based on sorted data must be applied back to the original structure. This article provides a thorough examination of how to obtain the index permutation after sorting, complete with technical examples and explanations.

Understanding Index Permutation in Sorting

Conceptual Overview

When you sort a list or array, the primary objective is to reorder the elements according to some criteria (numerical or lexicographical order, for example). However, in many cases, having a record of the original indices is useful. Index permutation refers to the sequence of indices in the original data that would produce the sorted data when applied.

Example

Consider a list `A` with elements `[40, 10, 30, 20]`. After sorting, the list becomes `[10, 20, 30, 40]`. The corresponding index permutation is `[1, 3, 2, 0]`:

• `A[1] = 10` maps to the first position after sorting.
• `A[3] = 20` maps to the second position.
• `A[2] = 30` maps to the third position.
• `A[0] = 40` maps to the fourth position.

Here's a simple table illustrating the original list, sorted list, and index permutation:

Implementing Index Permutation

Python Implementation

In Python, obtaining index permutation after sorting can be done efficiently using the `sorted()` function with the `key` parameter mapped to indices.

• We use `sorted(range(len(A)), key=lambda i: A[i])` which sorts the indices based on the values at those indices.
• The generated index permutation `[1, 3, 2, 0]` accurately maps the original indices to the sorted list.
• `np.argsort()` returns the indices that would sort the array.
• Advantageous for large arrays due to its optimized C implementations under the hood.