Sorting in linear time?

Question

Given an input set of n integers in the range [0..n^3-1], provide a linear time sorting algorithm.

This is a review for my test on thursday, and I have no idea how to approach this problem.

Could you check the question again? N vs n? [0..n^31] vs [0..2^31] vs [0..2^32-1]? — Daniel Brückner, Apr 14 '09 at 22:40
@danbruc - Good point. Also, revision 1 says [0..n^3-1] - why is it [0..n^31] now? — John Rasch, Apr 15 '09 at 00:22
I have no idea why this changed. I don't remember ever updating. — Stefan Kendall, Apr 15 '09 at 13:32
since the numbers are **equi-distant**, an [index-sort (custom sorting algorithm, using re-indexing)](http://foo123.github.io/examples/sorting-algorithms/#action=test&sorting_algorithm=IndexSort%20%28custom%29&data_size=20000&data_type=range&pre_sort_state=shuffled) can sort in strictly linear time and constant space (even if input includes duplicates) — Nikos M., Aug 20 '15 at 10:32
You can also use sleep sort. For each number do `sleep(value); print (value)`. ;) — Chris Hasiński, Sep 21 '16 at 22:27

score 24 · Answer 1 · answered Apr 14 '09 at 22:26

24

Have a look at radix sort.

answered Apr 14 '09 at 22:26

Reunanen

7,921
2
35
57

2

Just a caveat, radix sort is only linear if you have a fixed max length for your keys... since you have a range of integers, then yes, it can be linear, but this won't always be the case. – Dan Lew Apr 14 '09 at 22:37
1

This is also known as "bucket sort". – GoatRider Apr 14 '09 at 23:23
2

With the range of n d-digit numbers being in [0, n^3 - 1], then the number of digit d is 3log(n) and the algorithm will run in O(dn) => O(nlog(n)). Radix sort is not a linear solution. – Marsellus Wallace Mar 10 '13 at 19:22
1

@GoatRider bucket sort is different from radix sort because it runs in linear time when the input is drawn from a uniform distribution while radix sort runs in linear time when the number of digits in the numbers (or keys in the elements) is constant... – Marsellus Wallace Mar 10 '13 at 19:24
@MarsellusWallace, could you expand on when radix sort is linear? Even with fixed number of digits, wouldn't it be O(n log n) time? – sprajagopal Jul 28 '21 at 12:13

score 24 · Accepted Answer · answered Apr 14 '09 at 22:29

24

Also take a look at related sorts too: pigeonhole sort or counting sort, as well as radix sort as mentioned by Pukku.

answered Apr 14 '09 at 22:29

Ray Hidayat

16,055
4
37
43

3

Dont you think n^3-1 is a little too large to use counting sort? if n=100 you would have 100^3 space just to sort. He needs to change the base of the integers and use Radix sort. – unj2 Apr 21 '09 at 15:47
1

With the range of n d-digit numbers being in [0, n^3 - 1], then the number of digit d is 3log(n) and the algorithm will run in O(dn) => O(nlog(n)). Radix sort is not a linear solution. Also, pigeonhole is not suitable either because the number of elements is not "approximately the same" of the number of possible keys.. – Marsellus Wallace Mar 10 '13 at 19:21

score 15 · Answer 3 · answered Apr 14 '09 at 23:46

15

When people say "sorting algorithm" they often are referring to "comparison sorting algorithm", which is any algorithm that only depends on being able to ask "is this thing bigger or smaller than that". So if you are limited to asking this one question about the data then you will never get more than n*log(n) (this is the result of doing a log(n) search of the n factorial possible orderings of a data set).

If you can escape the constraints of "comparison sort" and ask a more sophisticated question about a piece of data, for instance "what is the base 10 radix of this data" then you can come up with any number of linear time sorting algorithms, they just take more memory.

This is a time space trade off. Comparason sort takes little or no ram and runs in N*log(n) time. radix sort (for example) runs in O(n) time AND O(log(radix)) memory.

answered Apr 14 '09 at 23:46

Arthur Ulfeldt

90,827
27
201
284

You can do an in place radix sort – aaronman Dec 01 '13 at 20:25
1

@aaronman could you link to the linear time constant space sorting algorithm? – Arthur Ulfeldt Dec 16 '13 at 17:52
Sure, keep in mind when I say constant space it's in reference to the size of the range, the storage is not constant in regards to the size of what's being sorted (32bit v 64bit). here is a link ([radix](https://github.com/aaronjosephs/radix/blob/master/radix.cpp)) to my own implementation, the code is messy but it's the one named `msd16_radix`, it uses counting to do the sort in place, also it calls std::sort because it's faster for small arrays so my implementation isn't strictly inplace (if std::sort uses memory) but it is clear that it can be achieved inplace. – aaronman Dec 16 '13 at 21:28
Now that I look at your answer again you do mention that the space is proportional to the radix. I guess you threw me off because you say it's a tradeoff, but if your radix is 16 or even 256 it's totally negligible to an array that could be millions or even a billion elements – aaronman Dec 16 '13 at 21:57

Ash · Answer 4 · 2009-04-14T22:54:25.083

3

It's really simple, if n=2 and numbers are unique:

Construct an array of bits (2^31-1 bits => ~256MB). Initialize them to zero.
Read the input, for each value you see set the respective bit in the array to 1.
Scan the array, for each bit set, output the respective value.

Complexity => O(2n)

Otherwise, use Radix Sort:

Complexity => O(kn) (hopefully)

edited Apr 14 '09 at 22:54

answered Apr 14 '09 at 22:35

Ash

699
1
7
6

The question says n^31 and not 2^31. Further you assume that no number appears more than once. – Daniel Brückner Apr 14 '09 at 22:42
I'm assuming n=2. I think that's a typo. After all, we don't typically use other bases than 2. You're right, I'm (probably incorrectly) assuming numbers are not repeated! – Ash Apr 14 '09 at 22:52
danbruc, I don't know your background, but my answer is very valid and well balanced (if I may say so). – Ash Apr 15 '09 at 04:40
initialization does take more than `O(n)` in this way...(Yet one would argue that OS could provide zeroed pages yeah... – phoeagon Sep 17 '13 at 15:36

score 3 · Answer 5 · answered Apr 14 '09 at 22:35

3

wikipedia shows quite many different sorting algorithms and their complexities. you might want to check them out

answered Apr 14 '09 at 22:35

ent

59
2

score 2 · Answer 6 · answered Nov 14 '12 at 17:37

2

Think the numbers as three digit numbers where each digit ranges from 0 to n-1. Sort these numbers with radix sort. For each digit there is a call to counting sort which is taking Theta(n+n) time, so that the total running time corresponds to Theta(n).

answered Nov 14 '12 at 17:37

Doğukan Çağatay

147
1
5

Sanjaya R · Answer 7 · 2016-08-23T19:18:38.520

2

A Set of a limited range of numbers can be represented by a bitmap of RANGE bits. In this case, a 500mb bitmap, so for anything but huge lists, you'd be better off with Radix Sort. As you encounter the number k, set bitmap[k] = 1. Single traversal through list, O(N).

edited Aug 23 '16 at 19:18

answered Apr 14 '09 at 22:33

Sanjaya R

6,246
2
17
19

Note that n might not equal 2. – Reunanen Apr 14 '09 at 22:36

score -2 · Answer 8 · edited Mar 16 '16 at 16:47

-2

alike algo is possible:

M;// unsorted array
lngth; //number items of M
for(int i=0; i < lngth; i++)sorted[M[i]];

It's alone possible algo for linear complexity, but it has complexity O(k*N) by ram (N - number array elements, k -- element's len)

edited Mar 16 '16 at 16:47

timrau

22,578
4
51
64

answered Apr 15 '09 at 00:06

Sorting in linear time?

8 Answers8

Linked

Related