Bucket sort

Question

1. Is bucket sort always stable  or does it depend on the sorting subroutine used by bucket sort toe sort the buckets?

2. Bucket sort is always NOT inplace.Is this correct?

Answer 1

a)I think its always stable because stable means maintaing the same order as the input

two vales that are similar arive in input

then first which arrived remains frirst and the next arrived will be next in order

In bucket sort a linked list is maintained and it maintains the same order as input

So i tink its always stable am not sure

b)Its not inplace because we create a separate array to link the lements in order

Answer 2

it is stable sort. stability of bucket sort not dependent on what we are using to sort bucket. but time complexity dependent

Bucket sort is mainly useful when input is uniformly distributed over a range. When the input contains several keys that are close to each other (clustering), those elements are likely to be placed in the same bucket, which results in some buckets containing more elements than average. The worst-case scenario occurs when all the elements are placed in a single bucket. The overall performance would then be dominated by the algorithm used to sort each bucket, which is typically O(N^2) insertion sort.making bucket sort less optimal than O(nlog(n) comparison sorting like quick sort.

it is not inplace sorting.

source

https://en.wikipedia.org/wiki/Bucket_sort