The Inversions of a List (Q7361696)
From MaRDI portal
!
This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:
AFP entry List_Inversions
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | The Inversions of a List |
AFP entry List_Inversions |
Statements
1 February 2019
0 references
Manuel Eberl
0 references
The Inversions of a List (English)
0 references
This entry defines the set of inversions of a list, i.e. the pairs of indices that violate sortedness. It also proves the correctness of the well-known O ( n log n ) divide-and-conquer algorithm to compute the number of inversions.
0 references
