{"id":18580,"date":"2017-08-09T15:06:26","date_gmt":"2017-08-09T19:06:26","guid":{"rendered":"https:\/\/mjtsai.com\/blog\/?p=18580"},"modified":"2017-08-09T15:06:26","modified_gmt":"2017-08-09T19:06:26","slug":"radix-sort-revisited","status":"publish","type":"post","link":"https:\/\/mjtsai.com\/blog\/2017\/08\/09\/radix-sort-revisited\/","title":{"rendered":"Radix Sort Revisited"},"content":{"rendered":"<p><a href=\"http:\/\/codercorner.com\/RadixSortRevisited.htm\">Pierre Terdiman<\/a>:<\/p>\n<blockquote cite=\"http:\/\/codercorner.com\/RadixSortRevisited.htm\">\n<p>Although the standard Radix Sort doesn&rsquo;t work very well with floating point values, this is something actually very easy to fix. In this little article I will review the standard Radix Sort algorithm, and enhance it so that:<\/p>\n<ul>\n<li>it sorts negative floats as well<\/li>\n<li>it has reduced complexity for bytes and words<\/li>\n<li>it uses temporal coherence<\/li>\n<li>it supports sorting on multiple keys<\/li>\n<\/ul>\n<p>[&#8230;]<\/p>\n<p>A Radix Sort is an apparently bizarre sort routine which manages to sort values without actually performing any comparisons on input data. That&rsquo;s why this sort routine breaks the theoretical lower bound of the O(N*logN) complexity, which only applies for comparison-based sorts. Radix is O(k*N), with k = 4 most of the time, and although this is not an in-place sort (i.e. it uses extra storage) it is so much faster than any other sorting methods it has become a very popular way of sorting data.<\/p>\n<\/blockquote>","protected":false},"excerpt":{"rendered":"<p>Pierre Terdiman: Although the standard Radix Sort doesn&rsquo;t work very well with floating point values, this is something actually very easy to fix. In this little article I will review the standard Radix Sort algorithm, and enhance it so that: it sorts negative floats as well it has reduced complexity for bytes and words it [&hellip;]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"apple_news_api_created_at":"","apple_news_api_id":"","apple_news_api_modified_at":"","apple_news_api_revision":"","apple_news_api_share_url":"","apple_news_coverimage":0,"apple_news_coverimage_caption":"","apple_news_is_hidden":false,"apple_news_is_paid":false,"apple_news_is_preview":false,"apple_news_is_sponsored":false,"apple_news_maturity_rating":"","apple_news_metadata":"\"\"","apple_news_pullquote":"","apple_news_pullquote_position":"","apple_news_slug":"","apple_news_sections":"\"\"","apple_news_suppress_video_url":false,"apple_news_use_image_component":false,"footnotes":""},"categories":[4],"tags":[289,263,669,71],"class_list":["post-18580","post","type-post","status-publish","format-standard","hentry","category-programming-category","tag-algorithm","tag-theory","tag-floating-point","tag-programming"],"apple_news_notices":[],"_links":{"self":[{"href":"https:\/\/mjtsai.com\/blog\/wp-json\/wp\/v2\/posts\/18580","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/mjtsai.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/mjtsai.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/mjtsai.com\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/mjtsai.com\/blog\/wp-json\/wp\/v2\/comments?post=18580"}],"version-history":[{"count":1,"href":"https:\/\/mjtsai.com\/blog\/wp-json\/wp\/v2\/posts\/18580\/revisions"}],"predecessor-version":[{"id":18581,"href":"https:\/\/mjtsai.com\/blog\/wp-json\/wp\/v2\/posts\/18580\/revisions\/18581"}],"wp:attachment":[{"href":"https:\/\/mjtsai.com\/blog\/wp-json\/wp\/v2\/media?parent=18580"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/mjtsai.com\/blog\/wp-json\/wp\/v2\/categories?post=18580"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/mjtsai.com\/blog\/wp-json\/wp\/v2\/tags?post=18580"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}