{"id":90209,"date":"2025-10-16T18:34:20","date_gmt":"2025-10-16T13:04:20","guid":{"rendered":"https:\/\/www.guvi.in\/blog\/?p=90209"},"modified":"2025-10-17T18:02:11","modified_gmt":"2025-10-17T12:32:11","slug":"bucket-sort-data-structures-and-algorithms","status":"publish","type":"post","link":"https:\/\/www.guvi.in\/blog\/bucket-sort-data-structures-and-algorithms\/","title":{"rendered":"Bucket Sort in DSA: A Comprehensive Tutorial"},"content":{"rendered":"\n

Sorting is one of the most fundamental problems you\u2019ll learn in computer science, and most people are introduced to it through algorithms like Bubble Sort, Insertion Sort, or Merge Sort.<\/p>\n\n\n\n

But there\u2019s another algorithm that often gets overlooked, even though it can outperform many common sorting techniques under the right conditions: Bucket Sort.<\/p>\n\n\n\n

It\u2019s a simple idea with powerful implications, especially when your data is distributed in a predictable way. Let\u2019s break it down in a way that actually makes sense, even if you\u2019re just getting started with algorithms in this article!<\/p>\n\n\n\n

What Is Bucket Sort?<\/strong><\/h2>\n\n\n\n
\"What<\/figure>\n\n\n\n

Bucket Sort is a distribution-based sorting algorithm <\/strong>from the world of data structures and algorithms<\/a>. That means it relies on how the values are spread out rather than comparing every element to every other element.<\/p>\n\n\n\n

Bucket Sort doesn\u2019t think the same way traditional comparison-based algorithms do. Instead of comparing pairs of elements one at a time, it groups elements into different \u201cbuckets\u201d based on their value range. Once the data is organized into buckets, each bucket is sorted individually, and then all the buckets are combined back in order to get the final result.<\/p>\n\n\n\n

Here\u2019s the basic process:<\/p>\n\n\n\n

    \n
  1. Divide the input into several buckets.<\/li>\n\n\n\n
  2. Distribute each element into the appropriate bucket based on its value.<\/li>\n\n\n\n
  3. Sort each bucket individually.<\/li>\n\n\n\n
  4. Concatenate all buckets to produce the final sorted array.<\/li>\n<\/ol>\n\n\n\n

    The key insight is that sorting many small groups is often faster than sorting one large group.<\/p>\n\n\n\n

    Why Bucket Sort Works<\/strong><\/h3>\n\n\n\n

    Imagine you\u2019re sorting students by their exam scores out of 100. Instead of sorting the entire list directly, you could create buckets such as 0\u20139, 10\u201319, 20\u201329, and so on. <\/p>\n\n\n\n

    Each student goes into the bucket that matches their score range. Once the scores are bucketed, each group is already partially organized by range. Sorting inside each bucket becomes easier and faster.<\/p>\n\n\n\n

    This approach leverages knowledge about the distribution of data. If you know your values fall within a certain range and are somewhat evenly spread out, Bucket Sort becomes extremely efficient.<\/p>\n\n\n\n

    Step-by-Step Breakdown of the Bucket Sort Algorithm<\/strong><\/h2>\n\n\n\n
    \"Step-by-Step<\/figure>\n\n\n\n

    Understanding the idea is helpful, but let\u2019s look at how the algorithm actually executes.<\/p>\n\n\n\n

    Step 1: Create Buckets<\/strong><\/h3>\n\n\n\n

    You predefine a certain number of buckets. Each bucket represents a specific range of values. The number of buckets is important; you don\u2019t want them too large or too small.<\/p>\n\n\n\n

    Step 2: Distribute the Elements<\/strong><\/h3>\n\n\n\n

    Each element from the input goes into a specific bucket based on its value. The mapping from value to bucket is usually done by a simple formula.<\/p>\n\n\n\n

    Step 3: Sort Each Bucket<\/strong><\/h3>\n\n\n\n

    Once all elements are distributed, each bucket is sorted individually. Because buckets are smaller than the original list, sorting them is faster.<\/p>\n\n\n\n

    Step 4: Merge the Buckets<\/strong><\/h3>\n\n\n\n

    Finally, the sorted buckets are concatenated to form the fully sorted array.<\/p>\n\n\n\n

    That\u2019s the core of the bucket sort algorithm. It\u2019s conceptually simple once you see it laid out this way.<\/p>\n\n\n\n

    If you want a platform that actually teaches DSA in a structured, beginner-friendly way while also giving you practical coding experience, consider enrolling in HCL GUVI\u2019s DSA for Programmers Course<\/a> that is designed specifically for learners who want clarity instead of confusion. It explains concepts in simple terms and guides you from basics to advanced topics step-by-step. <\/p>\n\n\n\n

    Basic Python Implementation of Bubble Sort<\/strong><\/h2>\n\n\n\n

    Let\u2019s start with the most common bucket sort scenario in Python<\/a>, sorting floating-point numbers in the range 0 to 1.<\/p>\n\n\n\n

    def bucket_sort(arr):\n\n    if len(arr) == 0:\n\n        return arr\n\n    # 1. Create buckets\n\n    buckets = [[] for _ in range(len(arr))]\n\n    # 2. Distribute elements\n\n    for num in arr:\n\n        index = int(num * len(arr))  # Determine bucket index\n\n        buckets[index].append(num)\n\n    # 3. Sort each bucket\n\n    for i in range(len(buckets)):\n\n        buckets[i].sort()\n\n    # 4. Concatenate buckets\n\n    sorted_arr = []\n\n    for bucket in buckets:\n\n        sorted_arr.extend(bucket)\n\n    return sorted_arr\n\ndata = [0.42, 0.32, 0.23, 0.52, 0.25, 0.47]\n\nprint(bucket_sort(data))<\/code><\/pre>\n\n\n\n
    This example illustrates the purest form of bucket sort. It assumes all values are between 0 and 1 and maps them directly to buckets by scaling.<\/p>\n\n\n\n
    Know how Python helps DSA to a great extent by reading – DSA with Python: Understand the Foundations of Coding<\/a><\/p>\n\n\n\n
    But What If the Values Are Integers?<\/strong><\/h3>\n\n\n\n
    Bucket sort can handle integers, too, but we need to think differently. Instead of multiplying values to map them into buckets, we can use bucket ranges.<\/p>\n\n\n\n
    def bucket_sort_integers(arr, bucket_size=5):\n\n    if len(arr) == 0:\n\n        return arr\n\n    min_value = min(arr)\n\n    max_value = max(arr)\n\n    bucket_count = (max_value - min_value) \/\/ bucket_size + 1\n\n    buckets = [[] for _ in range(bucket_count)]\n\n    for num in arr:\n\n        index = (num - min_value) \/\/ bucket_size\n\n        buckets[index].append(num)\n\n    sorted_arr = []\n\n    for bucket in buckets:\n\n        sorted_arr.extend(sorted(bucket))\n\n    return sorted_arr\n\ndata = [42, 32, 23, 52, 25, 47, 15, 10]\n\nprint(bucket_sort_integers(data))<\/code><\/pre>\n\n\n\n
    Here, we\u2019re grouping values based on ranges. Each bucket handles a slice of the number line.<\/p>\n\n\n\n
    Why Use Insertion Sort Inside Buckets?<\/strong><\/h3>\n\n\n\n
    You might wonder why insertion sort is used inside buckets, and that\u2019s because insertion sort is often chosen inside buckets. After all, buckets usually contain only a few elements. For small datasets, insertion sort is efficient, simple, and stable. <\/p>\n\n\n\n
    But you\u2019re not locked into using insertion sort. You can sort buckets using quicksort, mergesort, or even Python\u2019s built-in sorted() if that\u2019s easier. The algorithm is flexible.<\/p>\n\n\n\n
    Time and Space Complexity Analysis of Bucket Sort<\/strong><\/h2>\n\n\n\n
    The time complexity of bucket sort depends on how the elements are distributed.<\/p>\n\n\n\n
    Best case:<\/strong> All elements are spread evenly across buckets, and each bucket has just a few elements. Sorting each bucket is fast, leading to near O(n + k)<\/strong> time, where k is the number of buckets.<\/p>\n\n\n\n
    Average case:<\/strong> Similar to the best case, assuming uniform distribution. The algorithm remains efficient.<\/p>\n\n\n\n
    Worst case:<\/strong> All elements land in the same bucket. Now, you\u2019re essentially just sorting a normal list using whatever algorithm you used internally, often O(n\u00b2) if you used insertion sort.<\/p>\n\n\n\n
    Space Complexity<\/strong><\/h3>\n\n\n\n
    Bucket sort requires additional memory for the buckets. In total, it uses about O(n + k) space, where n is the number of input elements and k is the number of buckets. This is more memory than in-place sorting algorithms like quicksort.<\/p>\n\n\n\n
    Learn more about complexities in DSA by reading our blog – Understanding Complexity Analysis in Data Structures<\/a><\/strong><\/p>\n\n\n\n
    When Bucket Sort Works Best?<\/strong><\/h2>\n\n\n\n
    Bucket sort shines when:<\/p>\n\n\n\n