Is this implementation of Bucket-Sort considered "in-place"?

Question

Consider the following implementation of bucket-sort:

Algorithm BucketSort(S)
   input:  Sequence S of items with integer keys in range [0,N-1]
   output: Sequence S sorted in nondecreasing order of keys.

   let B be an array of N sequences, each of which is initially empty
   for each item x in S do
       let k be the key of x
       remove x from S and insert it at the end of bucket (sequence) B[k].
   for i←0 to N-1 do
       for each item x in sequence B[i] do
           remove x from B[i] and insert it at the end of S.

Is this implementation considered "In-Place"?

My textbook gives the following definition for "In-Place":

Remember that a sorting algorithm is in-place if it uses only a constant amount of memory in addition to that needed for the objects being sorted.

Now, I know the above algorithm uses O(n+N) memory, where N is the upper bound on the range. However, and I may be wrong, I think N would be a constant, even if it is a large one. So I'm guessing it is "in-place" per this definition but I'm unsure.

So given the above algorithm and definition of "in-place", is this implementation considered in-place?

Answer 1

Bucketsort is definitely not an "in-place" sorting algorithm.

The whole idea is that elements sort themselves as they are moved to the buckets. In the worst of the good cases (sequential values, but no repetition) the additional space needed is as big as the original array.

Answer 2

The number of buckets N is only bounded (after mapping the keys) by the length n of the input sequence S because every item in S might have a different key. Hence the algorithm requires linear additional space and is in consequence not in-place. If the keys are not remapped, the additional space is unbound by n.

Answer 3

The algorithm you have listed is decidedly not in-place.

You have another pointer (B) which must GROW to the same size as S, but is not in-place with S for any reason. Because of this you must have at least O(S) extra space. Just because you are removing the values from S does not keep you from still needing the same amount of space in another variable B.

Also just because the number of buckets might be constant doesn't mean you can forget that all elements in S must end up in a different place (B). Note the case where len(S) > N.

If you want to do an in-place sort, you need to keep all your elements in S and shuffle them around such that the constant extra space is a temporary holder for a swap routine and possibly some stack memory if you are using a recursive solution.