5 votes

Radix sort with benchmarks

There's an opaque magic number here, that reduces portability: putchar(48+(int)(u%10)); I think that was intended to be '0',...
Toby Speight's user avatar
  • 74.4k
5 votes

Sorting an array of positive integers including 0 much faster than Radix Sort

I think you re-invented counting sort, but with some small differences. Also you probably need to sort your sparse array keys before iterating over them so that's O(k log k) at least unless your ...
Cedric's user avatar
  • 216
5 votes
Accepted

C++ - Radix sort implementation

A vector is usually the best data structure to use unless you have a compelling reason to use something else. Since you know how many buckets you need, one slight improvement you can make to your ...
1201ProgramAlarm's user avatar
5 votes

Implementing LSD radix sort

An important thing about sorting is that it has to be fast and that it does not fill your entire heap space. That's why quicksort often is prefered before merge sort. And I think that your code is ...
Sam Segers's user avatar
4 votes
Accepted

Implement LSD radix sort in python

1. Introduction In this answer I'm just going to look at the function counting_sort. You'll see that there's plenty here for one answer. 2. Review There's no ...
Gareth Rees's user avatar
  • 49.6k
4 votes
Accepted

Implementing RadixSort using JavaScript

Your code is not finished. I could not say this is a finished bit of code as it simply does not work. A simple test, a random set of integers and comparing it to the result of the standard sort ...
Blindman67's user avatar
  • 21.6k
4 votes

Radix sort implementation

Nice question.... but, you're not doing a Radix Sort, but instead you're doing a Counting Sort As it happens, a counting sort is probably the best sort algorithm you could choose for this problem, so ...
rolfl's user avatar
  • 97.3k
4 votes
Accepted

Radix Sort Efficiency

Post line-oriented timings from a profiling run, please. Where does it actually spend its time? Curly braces {} are good for you, even when your for or ...
J_H's user avatar
  • 21.9k
4 votes
Accepted

MSD Quick Radix Sort in Place in C++, Object/Pointer Oriented

Review: ...
user673679's user avatar
  • 11.6k
3 votes

Radix Sort: A C++ version

In addition to JDługosz's answer: Use std::size_t Use it for index, as the value type of the array ...
G. Sliepen's user avatar
3 votes

Radix Sort: A C++ version

😀 First, it's good to see someone use iterator pairs and (somewhat) generic code, as opposed to the usual hard-coded collections being passed. Your View templates ...
JDługosz's user avatar
  • 11.3k
3 votes
Accepted

Radix sort is deceiving

Well, I guarantee that qsort doesn't start with a heap allocation. Benchmark several different sizes of array and graph the results, to see where the lines hit the ...
Quuxplusone's user avatar
  • 19.3k
3 votes
Accepted

MSD radix sort in C++

Use System costants as appropriate This is already defined by the Library: static constexpr size_t BITS_PER_BYTE = 8; The number of bits in a byte is: ...
Martin York's user avatar
  • 94.6k
3 votes

Radix sort (LSD) and counting sort

I found a list a few things that you could improve, but nothing that would significantly change the way your sorts work: At the end of the counting sort, you could use ...
Morwenn's user avatar
  • 19.9k
3 votes

Fast portable, parallel MSD radix sort for unsigned keys in C89

Consider using C11 thread support You are making your code compatible with C89, however that is a standard that is more than 30 years old, and we have advanced since then. C11 introduced support for ...
G. Sliepen's user avatar
2 votes
Accepted

Parallel MSD radix sort in Java

Very nice. private static final int THREAD_THRESHOLD = 65536; private static final int MERGESORT_THRESHOLD = 4096; These seem arbitrary. THREAD_THRESHOLD is ...
J_H's user avatar
  • 21.9k
2 votes

Implementing RadixSort using JavaScript

I am not JavaScript expert, still working on. Just share some tips. Things to improve I read Testable JavaScript and learned a few thing about choosing good test case for your code. Test case: <...
Jianmin Chen's user avatar
  • 2,396
2 votes

Radix Sort speed improvement

I never found a code that was simple and easy to understand yet wasn't any slower Note the order. Start readable. Start with What shall this be good for?: (doc)comment your code. No slower than ...
greybeard's user avatar
  • 6,286
2 votes

Radix sort implementation

Three comments: You are performing a lot of standard array manipulations for which there are implementations in the standard library. It may be faster to use this implementations; it will certainly ...
Jules's user avatar
  • 421
2 votes
Accepted

Radix sort implementation in JS (LSD)

Well!! First off I will say that is an impressive amount of work for a sort, lots of research and references. BUT!!! I am not going to sugar coat the rest. The implementation is overly complex and ...
Blindman67's user avatar
  • 21.6k
2 votes

Radix Sort Efficiency

The actual specifier is MSD (most-significant digit) and not MSB (most-significant bit, I suppose). What comes to performance, years ago I wrote a MSD radix sort that takes a parameter, call it \$d\$. ...
coderodde's user avatar
  • 27.6k
2 votes

Counting Radix Sort: A C++ version

The assumption that CHAR_BIT is 8 can be avoided. I'm not convinced it's necessary to use the exact-width type std::uint64_t. ...
Toby Speight's user avatar
  • 74.4k
2 votes
Accepted

Radix sort function in R

Putting these comments into an answer... As pointed out, it will be a tall order to beat or even approach the computation times of the native sort function, as it ...
flodel's user avatar
  • 3,525
2 votes

Radix sort with benchmarks

Not much left after @Toby Speight review. Bug? Code has a mysterious & 0xff. Perhaps % count_size? ...
chux - Reinstate Monica's user avatar
2 votes
Accepted

Fast portable, parallel MSD radix sort for unsigned keys in C89

The function parallel_radix_sort_impl() is over 400 lines of code. There must be some way to break this up into multiple functions. This is way too complex, and too ...
pacmaninbw's user avatar
  • 23.8k
1 vote
Accepted

Improving performance of radix sort

Some general review: We're missing an include of <string.h> for memset(). There are some constants that aren't obviously ...
Toby Speight's user avatar
  • 74.4k
1 vote

Radix Sort function

Firstly, please put the headers: #include <vector> #include <algorithm> #include <queue> I wonder if you could may be do this set up in a ...
Suryasis Paul's user avatar
1 vote

Radix Sort Speed

#flattened list, reusing lst to save memory lst = [] That doesn't save memory. The caller of the current helper ...
Kelly Bundy's user avatar
  • 3,134
1 vote

MSD Radix sort in Place in c++, Object/Pointer Oriented

Note: I wrote this answer in response to your other post, which was deleted just before I posted. However, it nearly all applies to this code too, so here it is: ...
user673679's user avatar
  • 11.6k
1 vote
Accepted

LSD radix sort (force avoid div or idiv compiler instruction) in C++

Avoid macros There is no need to make modpow2 a macro. Make it a function instead: ...
G. Sliepen's user avatar

Only top scored, non community-wiki answers of a minimum length are eligible