Welcome to Lesson 18!Learning ObjectivesBy the end of this class, you should know...Bucket sortAnnouncementsLast Quiz WednesdayWill ask you to trace merge sort in actionWill ask you to write the pseudocode for mergesort (NOT the helper function merge)Heap QuestionsAVL Tree QuestionsProject Report 5 due Wednesday, December 2Assignment 5 due ThursdayProject Presentations next weekTeams 1-4 todayTeams 5-8 on WednesdayBucket SortNo longer a comparison-based sorting algorithmInstead a parallel sorting algorithmSort values into individual "buckets"Re-arrange them within the bucket into a sorted orderCombine buckets back into array or listHere we scatter (into buckets) and gather (back into the array) rather than divide and conquerMainly useful when input is uniformly distributed over a rangeVisualizing Bucket SortScatter elements into their respective binsSort elements inside of bins and return to the arrayImage sourceBucket Sort In Under 40 SecondsVideoBucket Sort PseudocodebucketSort(A[], k) //pass in k = number buckets    List buckets[k]    for i = 0 to array_size-1        insert array[i] into buckets[correctBucket(array[i])]    for i = 0 to k-1        sort(buckets[i])    return concat(buckets[0]...buckets[k-1])    Time Complexity of Bucket SortBest Case: O(n + k) //k = number of bucketsWorst Case: O(n2) //if all elements in one bucket and sort with slow sorting algorithmAverage Case: O(n + k)Project PresentationsTeams 1- 4