0
$\begingroup$

I imagined a sorting algorithm that sorts an array in O(r) time, where r is the range. Is this already an algorithm (if so, which?), or have I made a mistake calculating the running time (probably).

  1. Create an array going consecutively from the smallest element to the largest element.
  2. Loop over the unsorted array and for each element mark the same element in the generated array. Since the list is sorted, we can jump to each element in O(1) time [number three is the third element in the generated array].
  3. Remove all elements that are unmarked from the generated array.

If this can really run in O(r), then since for most datasets the range is not larger than the number of elements, this would be faster than merge sort or any other sorting algorithm.

| cite | improve this question | |
$\endgroup$
  • 1
    $\begingroup$ Your algorithm is close to Counting Sort $\endgroup$ – Prateek Apr 4 '16 at 23:12
  • $\begingroup$ @Prateek Counting Sort should be used more often; especially when the numbers are consecutive. $\endgroup$ – noɥʇʎԀʎzɐɹƆ Apr 4 '16 at 23:25
  • $\begingroup$ Absolutely, the only thing is that we must know the range of numbers before hand. $\endgroup$ – Prateek Apr 4 '16 at 23:59
  • 1
    $\begingroup$ This gets at issues of the model of running time. On a Turing Machine, you cannot jump to the $k$th element in $O(1)$ time. Maybe you can probably do so in the RAM model, not sure. Also, I think you could implement "remove all elements that are unmarked" in linear time if you're allowed to jump to memory addresses in constant time, but it's at least not immediately obvious how. $\endgroup$ – usul Apr 5 '16 at 5:11
  • $\begingroup$ @usul Looping over the array and remove it if it is unmarked works on a Turing Machine. $\endgroup$ – noɥʇʎԀʎzɐɹƆ Apr 5 '16 at 22:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.