Year-end appeal: Please make a donation to the OEIS Foundation to support ongoing development and maintenance of the OEIS. We are now in our 61st year, we have over 378,000 sequences, and we’ve reached 11,000 citations (which often say “discovered thanks to the OEIS”).
%I #3 Dec 16 2016 16:23:35
%S 0,1,3,5,8,11,15,19,24,30,36,42,49,56,64,73,82,91,101,111,122,134,146,
%T 158,171,185
%N Median number of comparisons used by insertion sort on n (distinct) elements.
%C The frequencies of the number of comparisons are given by sequence A129178, so if Sum_{k=0..i-1} A129178(n,k) < n!/2 and Sum_{k=0..i} A129178(n,k) > n!/2, then the median is entry i, which corresponds to n(n-1)/2-i comparisons.
%C Close to average number of comparisons: A159324(n)/n!
%e For n=3, permutations 123,132,213,231,312,321 require 3,3,3,2,3,2 comparisons respectively, so the median is 3.
%Y Cf. A129178, A159323, A159324.
%K nonn
%O 1,3
%A Harmen Wassenaar (towr(AT)ai.rug.nl), Apr 10 2009