X hits on this document

Powerpoint document

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

67 views

0 shares

0 downloads

0 comments

18 / 28

Comp 122

linsort - 18

Lin / Devi

Comp 122

Algorithm Analysis

Each pass over n d-digit numbers then takes time (n+k). (Assuming counting sort is used for each pass.)

There are d  passes, so the total time for radix sort is (d (n+k)).

When d is a constant and k = O(n), radix sort runs in linear time.

Radix sort, if uses counting sort as the intermediate stable sort, does not sort in place.  

»

If primary memory storage is an issue, quicksort or other sorting methods may be preferable.

Document info
Document views67
Page views67
Page last viewedTue Dec 06 00:24:44 UTC 2016
Pages28
Paragraphs427
Words1924

Comments