Radix Sort

Definitions

1. A non-comparison sorting algorithm that distributes elements into buckets based on individual digits or characters, processing from least-significant to most-significant digit (LSD) or vice versa (MSD). It runs in O(nk) time where k is the number of digits, making it faster than comparison sorts for fixed-width integers or strings.

   In plain English: A sorting method that organizes items by looking at one digit at a time, from rightmost to leftmost, rather than comparing pairs of items.

   Example: "We used radix sort on the 64-bit integer keys because comparison-based sorts couldn't keep up with 100 million records."

Related Terms

• Backtracking
• Big-O
• Binary Tree
• Graph
• Hash Table
• Merge Sort
• Quick Sort
• Bucket Sort