CODEWITHSUNDEEP
algorithmsorting
crownZ
crownZ

Reputation: 69

Is Bucket Sort stable when using Quick Sort in Bucket Sort?

Recently, I am learning sorting algorithm. When learning Bucket Sort, I have the question of title. I know Quick Sort is unstable, and wiki says Bucket Sort is stable at here. But is it still stable when using Quick Sort in Bucket Sort? I can't imagine what will happen, can anyone help me? Thanks a lot.

Upvotes: 1

Views: 757

Answers (1)

MBo
MBo

Reputation: 80287

Any unstable sort may change item order in a bucket. When you merge buckets, this violated order remains.

Imagine we have buckets 0..9 with point (5,5) and bucket 20..29 contains points (22,3), (21,14), (22,7). After unstable sort (by the first key) we can see order like (21,14), (22,7), (22,3) (just example). After merging we can see

 (5,5), (21,14), (22,7), (22,3)

where mutual order of points with x=22 has been changed

If we use, for example, insertion sort inside buckets, we have guarantee that result is

 (5,5), (21,14), (22,3), (22,7)

Upvotes: 2

Related Questions