login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A159325 Median number of comparisons used by insertion sort on n (distinct) elements. 0
0, 1, 3, 5, 8, 11, 15, 19, 24, 30, 36, 42, 49, 56, 64, 73, 82, 91, 101, 111, 122, 134, 146, 158, 171, 185 (list; graph; refs; listen; history; text; internal format)
OFFSET

1,3

COMMENTS

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.

Close to average number of comparisons: A159324(n)/n!

LINKS

Table of n, a(n) for n=1..26.

EXAMPLE

For n=3, permutations 123,132,213,231,312,321 require 3,3,3,2,3,2 comparisons respectively, so the median is 3.

CROSSREFS

Cf. A129178, A159323, A159324.

Sequence in context: A213706 A078126 A024206 * A228848 A049706 A080415

Adjacent sequences:  A159322 A159323 A159324 * A159326 A159327 A159328

KEYWORD

nonn

AUTHOR

Harmen Wassenaar (towr(AT)ai.rug.nl), Apr 10 2009

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified June 14 05:10 EDT 2021. Contains 345018 sequences. (Running on oeis4.)