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).
- Create an array going consecutively from the smallest element to the largest element.
- 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].
- 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.