Random Wits

Life is too short for a diary

$ random wits
├── tags

├── bookshelf

├── resources

├── quotes

├── habits

└── about

Posts Tagged “radix sort”

Fri 20 Nov 2015

Quickly sort large file in linear time

Any deterministic general sorting algorithm has average case time complexity @L \Omega(n\log{}n) @L . However, certain sorting algorithm can run faster in @L O(n) @L but with limitation. Instead of comparision-based sort, each element is looked individually by its value. Radix sort is one fine example of integer sorting.

Suppose, we have large directory containing names of people in random order. The names need not be distinct. We need to sort the name in the ascending order. Also our algorithm should run in linear time. A sample of the input file is shown below...

Continue reading → code lsd radix sort sorting