Estimating the Error of a Permutational Central Limit Theorem

Motivated by two measures of presortedness, number of runs and oscillation of a permutation, related to the sorting problem, we derive an error bound for normal approximation to the distribution of Here, α ij 's are given real numbers and π is a uniformly distributed random permutation of {l,…, n }. The derivation is based on Stein's method.