Radix Sort – Data Structures and Algorithms Tutorials Medium 0 attempts
GeeksforGeeks ↗

Radix Sort – Data Structures and Algorithms Tutorials

Medium Sorting&Searching GeeksforGeeks

Sort an array of non-negative integers using Radix Sort — the digit-by-digit approach that repeatedly buckets numbers by one digit position (typically least significant first) using a stable sort, until every digit has been processed.

Input Format
Implement radixSort(arr). Inputs below show JavaScript function arguments; there is no stdin parsing.
Output Format
Return the result described in the statement.

Sample Input and Output

Example 1 · Run Sample

Input
arr = [170,45,75,90,802,24,2,66]
Output
[2,24,45,66,75,90,170,802]

Example 2

Input
arr = [0,0]
Output
[0,0]
Constraints
  • 1 <= N <= 10^5
  • 0 <= arr[i] <= 10^9
Test Cases (2)
Case 1
Args: [[170,45,75,90,802,24,2,66]] Expected: [2,24,45,66,75,90,170,802]
Case 2
Args: [[0,0]] Expected: [0,0]
Topics
Sorting&Searching

LSD Radix Sort

javascript
function radixSort(arr) {
  const max = Math.max(...arr);
  for (let exp = 1; Math.floor(max / exp) > 0; exp *= 10) {
    const buckets = Array.from({length:10}, ()=>[]);
    for (const n of arr) buckets[Math.floor(n/exp) % 10].push(n);
    arr = buckets.flat();
  }
  return arr;
}

Time: O(d × (n + k)) | Space: O(n + k)

Saved in this browser only. Private to you.

JavaScript