Sorting in O(n)

Revision en1, by Jrke, 2025-10-22 23:34:08

Ok, so first of all i don't know if it exist. But i will share my algorithm here only.

Motivation, Radix sort with base > 10?

so my motivation came when i though of why can't we use base 1e5 or 1e6 in radix sort? and i came up with following idea.

Most of the questions on CF have limit of values <=1e9. So my algorithm focuses majorily on that thing. let us define

Tags sorting, radix sort, cpp, optimizations

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en8 English Jrke 2025-10-23 16:33:47 943
en7 English Jrke 2025-10-23 08:59:41 0 (published)
en6 English Jrke 2025-10-23 08:58:44 1 Tiny change: 'nd memory.\n\nFor n ' -> 'nd memory. U\n\nFor n '
en5 English Jrke 2025-10-23 08:55:34 1881
en4 English Jrke 2025-10-23 00:05:08 0 Tiny change: ' = pref[x &mdash; 1] + live' -> ' = pref[x - 1] + live'
en3 English Jrke 2025-10-23 00:01:34 8
en2 English Jrke 2025-10-23 00:00:22 1231 Tiny change: 'ng idea.\n\nMost of ' -> 'ng idea.\nMost of '
en1 English Jrke 2025-10-22 23:34:08 391 Initial revision (saved to drafts)