X hits on this document

Powerpoint document

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

97 views

0 shares

0 downloads

0 comments

22 / 28

Comp 122

linsort - 22

Lin / Devi

Comp 122

Correctness of BucketSort

Consider A[i], A[j]. Assume w.o.l.o.g, A[i] A[j].

Then, n A[i] n A[j].

So, A[i] is placed into the same bucket as A[j] or into a bucket with a lower index.

»

If same bucket, insertion sort fixes up.

»

If earlier bucket, concatenation of lists fixes up.

Document info
Document views97
Page views97
Page last viewedFri Jan 20 08:10:21 UTC 2017
Pages28
Paragraphs427
Words1924

Comments