X hits on this document

Powerpoint document

Lower Bounds & Sorting in Linear Time - page 7 / 28

75 views

0 shares

0 downloads

0 comments

7 / 28

Comp 122

linsort - 7

Lin / Devi

Comp 122

Optimal sorting for three elements

Any sort of six elements has 5 internal nodes.

1:2

2:3

1:3

1:3

2:3

1,2,3

1,3,2

3,1,2

2,1,3

2,3,1

3,2,1

>

>

>

>

There must be a wost-case path of length ≥ 3.

Document info
Document views75
Page views75
Page last viewedThu Dec 08 16:55:09 UTC 2016
Pages28
Paragraphs427
Words1924

Comments