On Straight Selection Sort
Abstract:
The expected value of Bn = B'n - (n - 1), where B'n is the number of right-to-left maxima encountered by the straight selection sort, is well known to be (n+1)Hn - 2n, but the variance of Bn has remained unanalyzed. In this paper, we derive an exact formula for the variance of Bn, and show that it is
asymptotically equal to alpha n3/2(1 + o(1)), where alpha > 0 is an explicitly defined constant.