3

Let's say we have an array filled with long long unsigned int. The distance between each adjacent elements is small. For example we have : [0,1,0,1,0,1] We have another array of the same size and the distance between each adjacent element is now significant. We have then the following array : [1, 1000000000, 1, 1000000000, 1, 1000000000].

The last step is to sort the two arrays with the insertion sort or merge sort or quicksort. Is it possible that the processing time is longer for the second array because of the greater distance between elements ?

Thank you in advance !

1
  • If the "distance" is large, does it take longer to determine which value is larger? If not, what difference would it make? Commented Mar 10, 2017 at 18:56

1 Answer 1

5

Sorting algorithms like insertion sort, quicksort, and mergesort are called comparison sorts because they sort elements based purely on the relative order of those elements, not their absolute size. From the perspective of quicksort, mergesort, or insertion sort, the array [0, 1, 0, 1, 0] and [0, 100000, 0, 100000, 0] are completely identical, since they have no way of knowing that 100000 is "much bigger than" 1. The total number of operations performed to sort those arrays will be completely identical to one another. In fact, if you sort each array with those algorithms and watch the elements move around, you'll find that the exact same moves get performed.

If you're talking about sorting integers that fit into a single machine word, then the cost of a move is independent of the numeric value stored in that machine word. The cost of comparing those elements is likely also the same. I would therefore predict that you would see absolutely no difference in the time required to sort these arrays with those algorithms.

If there is any difference, it would mean that the processor you're using can compare or move numbers of different sizes in different amounts of time. To the best of my knowledge there are no real processor architectures that do this.

Now, on the other hand, sorting algorithms like counting sort or radix sort, which are not comparison sorts and do depend on the sizes of the numbers you're dealing with, could take longer to sort these arrays because they work either one digit at a time or by distributing into an array whose size depends on the sizes of the numbers in questions. In those cases, you should see a difference between the runtimes, provided that the algorithm you used was implemented well.

Sign up to request clarification or add additional context in comments.

2 Comments

"no real processor architectures that do this" (compare numbers in different time) --> certainly an 8-bit embedded processor would take less time to compare order of 64-bit integers 1 and 1000000000 than 0 and 1 unlike a 64-bit processor that would use constant time. Still a very good answer.
True but the OP did say long long int and the answer did properly qualify the claim with "If you're talking about sorting integers that fit into a single machine word." The answer was musing about architectures that would do faster single word comparisons when there were fewer borrow propagations, and yeah, I'd have to hazard a guess that such things are non-existent or painfully rare. :)

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.