# The Inversions of a List

 Title: The Inversions of a List Author: Manuel Eberl Submission date: 2019-02-01 Abstract: 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. BibTeX: @article{List_Inversions-AFP, author = {Manuel Eberl}, title = {The Inversions of a List}, journal = {Archive of Formal Proofs}, month = feb, year = 2019, note = {\url{https://isa-afp.org/entries/List_Inversions.html}, Formal proof development}, ISSN = {2150-914x}, } License: BSD License