Relationship between Amp and Mono

In this article, we analyze the relationship between the measure of disorder \(\mathit{Amp}\), which I introduced a while ago, and another measure of disorder: \(\mathit{Mono}\), the number of monotonic runs into which a sequence can be decomposed. Identity of \(\mathit{Mono}\) \(\mathit{Mono}\) is a measure of disorder originally described in [Sort Race][sort-race] by H. Zhang, B. Meng and Y. Liang: Intuitively, if \(\mathit{Mono}(X) = k\), then \(X\) is the concatenation of \(k\) monotonic lists (either sorted or reversely sorted). \(\mathit{Mono}\) is a natural extension of \(\mathit{Runs}\)1 which seeks to find sortedness in both ascending and descending sequences. From a sorting point of view, it is useful to quantify the number operations performed by natural mergesorts that and merge detect monotonic runs. A sorted sequence contains a single ascending run, so implementations of \(\mathit{Mono}\) might retrieve \(1\) to that number to obtain \(0\) for such a sequence (Mannila’s…