Why is the worst-case running time for bucket sort θ(n²)? What changes would you make to the algorithm so that its worst-case running time becomes O(nlgn)?

The worst-case scenario for bucket sort occurs when the distribution of elements is highly skewed, causing most of the elements to be placed in a single bucket. If all elements fall into one bucket, the sorting algorithm applied within that bucket determines the overall time complexity. If that sorting algorithm is insertion sort, the time complexity for sorting n elements within the bucket would be θ(n²).

Instead of using insertion sort (which has a worst-case time complexity of θ(n²)), we can use a more efficient sorting algorithm like merge sort or quicksort. Both merge sort and quicksort have an average-case time complexity of O(nlogn), and merge sort has a worst-case time complexity of O(nlogn). This change ensures that even if one bucket ends up with most of the elements, the sorting within that bucket is efficient.