Radix Sort

Learn about radix sort, an algorithm that operates on numbers digit by digit.

Start[missing "en.views.course_landing_page.sorting-algorithms.course_illustration" translation]
Chevron Left Icon
Radix Sort: Conceptual
Lesson 1 of 2
Chevron Right Icon
  1. 1

    Quick, which number is bigger: 1489012 or 54? It’s 1489012, but how can you tell? It has more digits so it has to be larger, but why exactly is that the case? Our number system was developed by 8t...

  2. 2

    The value of different positions in a number increases by a multiplier of 10 in increasing positions. This means that a digit '8' in the rightmost place of a number is equal to the value 8, but tha...

  3. 3

    So how does a radix sort use this base numbering system to sort integers? First, there are two different kinds of radix sort: most significant digit, or MSD, and least significant digit, or LSD. B...

  4. 4

    The most amazing feature of radix sort is that it manages to sort a list of integers without performing any comparisons whatsoever. We call this a non-comparison sort. This makes its performance ...

  5. 5

    Take a moment to review radix sort: - A radix is the base of a number system. For the decimal number system, the radix is 10. - Radix sort has two variants - MSD and LSD - Numbers are bucketed base...

  1. 1

    In our version of least significant digit radix sort, we're going to utilize the string representation of each integer. This, combined with negative indexing, will allow us to count each digit in a...

  2. 2

    In this implementation, we're going to build the radix sort naturally, from the inside out. The first step we're going to take is going to be our inner-most loop, so that we know we'll be solid whe...

  3. 3

    The least significant digit radix sort algorithm takes each number in the input list, looks at the digits of that number in order from right to left, and incrementally stuffs each number into the b...

  4. 4

    For every iteration, radix sort renders a version of the input list that is sorted based on the digit that was just looked at. At first pass, only the ones digit is sorted. At the second pass, the ...

  5. 5

    We have the interior of our radix sort, which right now goes through a list and sorts it by the first digit in each number. That's a pretty great start actually. It won't be hard for us to go over ...

  6. 6

    Now that we've finished writing our radix sort we're finished for the day... or are we?

How you'll master it

Stress-test your knowledge with quizzes that help commit syntax to memory

Pro Logo

Radix Sort

Start[missing "en.views.course_landing_page.sorting-algorithms.course_illustration" translation]