Name: Anonymous 2012-03-11 21:27
Sup /prog/,
So, I'm having trouble finding out what my professor meant by this, not sure if it's a typo because he often has typo's in his assignments. If the range was simply 1 to m, I would just use counting or bucket sort, but since it's 1 to m^2, I really have no clue. Thanks for any help I can get on this. Here's the problem:
Let x1, x2,…,xn be a sequence of integers in the range 1 to m^2. Describe an algorithm to sort this sequence in time O(n + m).
So, I'm having trouble finding out what my professor meant by this, not sure if it's a typo because he often has typo's in his assignments. If the range was simply 1 to m, I would just use counting or bucket sort, but since it's 1 to m^2, I really have no clue. Thanks for any help I can get on this. Here's the problem:
Let x1, x2,…,xn be a sequence of integers in the range 1 to m^2. Describe an algorithm to sort this sequence in time O(n + m).