Does length of number affects sorting time?

Question

I have a simple question does the length of numbers that need to be sorted affects the sorting time ?? Example: Suppose we need to sort 10 million 6 digit numbers (like: 204134) and 10 million 2/3 digit numbers(like: 24, 143) and to sort both the sets individually. Does the set with 6 digit numbers is gonna take more time than the the one with 2/3 digit numbers ?

I know the hardware use each logic gate for a single digit so 6 logic gates for 6 digits compared to 2/3 gates for other set but i don't know whether this affects the sorting time or not. Can someone explain me this. Helps will be appreciated. Thanks

Answer 1

The hardware works with bits, not with decimal digits. Furthermore, the hardware always works with the same fixed amount of bits (for a given operation); smaller values are padded. For example, a 32 bit CPU usually has 32 bit comparator units with exactly as much circuitry needed for 32 bit comparisons, and uses those regardless of whether the values currently being compared would fit into fewer bits.

Another issue with your thinking is that the exact amount of logic gates doesn't matter much for performance. The propagation time of individual gates is much smaller than a clock cycle, only rather complicated circuits with long dependency chains actually take longer than a single cycle (and even then it might be pipelined to still get a throughput of 1 op per cycle). A surprisingly large number of logic gates in sequence (and an virtually unlimited number of logic gates in parallel) can easily finish their work within one clock cycle. Hence, a smart 64 bit comparison doesn't take more clock cycles than a 8 bit one.

Answer 2

The short answer: It depends, but probably not

The longer answer: It's hard to know because you haven't said much about the hardware or the sorting algorithm. You mentioned later that you're using some MPI variant of Quicksort. So you're asking if there could be a performance difference between 6-bit numbers and 3-bit numbers due to the hardware. Well, if you pack those digits together then you're going to have better bandwidth when transferring the dataset from memory to the processor. Since you haven't mentioned anything about compacted arrays, I'll assume you're not doing this. Once the value is in the register it will have the same latency and throughput regardless of being 6 bits or 3 bits.

There are algorithms like radix sort that perform differently depending on the number of bits needed for your range of numbers. Since you're not using this, it doesn't apply.