A radix sort is a sorting algorithm that can rearrange integer representations based on the processing of individual digits in such a way that the integer representations are eventually in either ascending or descending order. Integer representations can be used to represent things such as strings of characters (names of people, places, things, the words and characters that you are reading now, dates, etc.) and specially formatted floating point numbers as well as integers. So, anything which can be represented as an ordered sequence of integer representations can be rearranged to be in order by a radix sort. In computer science and mathematics, a sorting algorithm is an algorithm that puts elements of a list in a certain order. ...

Most digital computers internally represent all of their data as electronic representations of binary numbers, so processing the digits of integer representations by groups of binary digit representations is most convenient. Two classifications of radix sorts are least significant digit (LSD) radix sorts and most significant digit (MSD) radix sorts. LSD radix sorts process the integer representations starting from the least significant digit and move the processing towards the most significant digit. MSD radix sorts process the integer representations starting from the most significant digit and move the processing towards the least significant digit. This article or section is not written in the formal tone expected of an encyclopedia article. ... This article or section is not written in the formal tone expected of an encyclopedia article. ...

The integer representations that are processed by sorting algorithms are often called "keys," which can exist all by themselves or be associated with other data. LSD radix sorts typically use the following sorting order: short keys come before longer keys, and keys of the same length are sorted lexicographically. This coincides with the normal order of integer representations, such as the sequence 1, 2, 3, 4, 5, 6, 7, 8, 9, 10. MSD radix sorts use lexicographic order, which is suitable for sorting strings, such as words, or fixed-length integer representations. A sequence such as "b, c, d, e, f, g, h, i, j, ba" would be lexicographically sorted as "b, ba, c, d, e, f, g, h, i, j". If lexicographic ordering is used to sort variable-length integer representations, then the representations of the numbers from 1 to 10 would be output as 1, 10, 2, 3, 4, 5, 6, 7, 8, 9, as if the shorter keys were left-justified and padded on the right with blank characters to make the shorter keys as long as the longest key for the purpose of determining sorted order.

Least significant digit radix sorts

A least significant digit (LSD) radix sort is a fast stable sorting algorithm which can be used to sort keys in lexicographic order. Keys may be a string of characters, or numerical digits in a given radix. The processing of the keys begins at the least significant digit, the rightmost digit, and proceeds to the most significant digit, the leftmost digit. The sequence in which digits are processed by a least significant digit (LSD) radix sort is the opposite of the sequence in which digits are processed by a most significant digit (MSD) radix sort. This article or section is not written in the formal tone expected of an encyclopedia article. ... In computer science and mathematics, a sorting algorithm is an algorithm that puts elements of a list in a certain order. ... In computer science and mathematics, a sorting algorithm is an algorithm that puts elements of a list in a certain order. ... In mathematics, the lexicographical order, or dictionary order, is a natural order structure of the cartesian product of two ordered sets. ... In computer programming and some branches of mathematics, strings are sequences of various simple objects. ... The radix (Latin for root), also called base, is the number of various unique symbols (or digits or numerals) a positional numeral system uses to represent numbers. ... This article or section is not written in the formal tone expected of an encyclopedia article. ... This article or section is not written in the formal tone expected of an encyclopedia article. ... This article or section is not written in the formal tone expected of an encyclopedia article. ... This article or section is not written in the formal tone expected of an encyclopedia article. ...

A least significant digit (LSD) radix sort operates in O(nk) time, where n is the number of keys, and k is the average key length. You can get this performance for variable-length keys by grouping all of the keys that have the same length together and separately performing an LSD radix sort on each group of keys for each length, from shortest to longest, in order to avoid processing the whole list of keys on every sorting pass. This article or section is not written in the formal tone expected of an encyclopedia article. ... Big O notation or Big Oh notation, and also Landau notation or asymptotic notation, is a mathematical notation used to describe the asymptotic behavior of functions. ...

A radix sorting algorithm was originally used to sort punched cards in several passes. A computer algorithm was invented for radix sort in 1954 at MIT by Harold H. Seward. In many newer applications requiring super speeds and massive memory, the computer radix sort is an improvement on (slower) comparison sorts. A CTR census machine, utilizing a punched card system. ... The Massachusetts Institute of Technology (MIT) is a private, coeducational research university located in Cambridge, Massachusetts. ... Harold H. Seward is a computer scientist and the developer of the radix sort algorithm in 1954 at MIT and counting sort. ...

LSD radix sorts have resurfaced as an alternative to other high performance comparison-based sorting algorithms (like heapsort and mergesort) that require Ω(n · log n) comparisons, where n is the number of items to be sorted. Comparison sorts can do no better than Ω(n · log n) execution time but offer the flexibility of being able to sort with respect to more complicated orderings than a lexicographic one; however, this ability is of little importance in many practical applications. A run of the heapsort algorithm sorting an array of randomly permuted values. ... In computer science, merge sort or mergesort is a sort algorithm for rearranging lists (or any other data structure that can only be accessed sequentially, e. ... A comparison sort is a particular type of sorting algorithm; a number of well-known algorithms are comparison sorts. ...

Each key is first figuratively dropped into one level of buckets corresponding to the value of the rightmost digit of each key. Each bucket preserves the original order of the keys as the keys are dropped into each bucket. There is a one-to-one correspondence between the number of buckets and the number of values that can be represented by a digit. Then, the process repeats with the next neighboring digit until there are no more digits to process. In other words:

1. Take the least significant digit (or group of bits, both being examples of radices) of each key.
2. Group the keys based on that digit, but otherwise keep the original order of keys. (This is what makes the LSD radix sort a stable sort).
3. Repeat the grouping process with each more significant digit.

The sort in step 2 is usually done using bucket sort or counting sort, which are efficient in this case since there are usually only a small number of digits. The radix (Latin for root), also called base, is the number of various unique symbols (or digits or numerals) a positional numeral system uses to represent numbers. ... In computer science and mathematics, a sorting algorithm is an algorithm that puts elements of a list in a certain order. ... Bucket sort is a sort algorithm that works by partitioning an array into a finite number of buckets and then sorting each bucket. ... Counting sort is a sorting algorithm which (like bucket sort) takes advantage of knowing the range of the numbers in the array to be sorted (array A). ...

When an LSD radix sort processes keys which all have the same fixed length, then the upper bound of the execution time is O(n), where n is the number of keys to be sorted. When processing fixed-length keys, some implementations of LSD radix sorts are slower than O(n · log n) comparison-based sorting algorithms, such as heap sort, unless a sufficiently large amount of input data is processed. What a sufficiently large amount of input data precisely is will vary from computer system to computer system and from implementation to implementation. If the keys used are short 2-byte integers, it is practical to complete the sorting with only two passes, processing 1 byte of each key per pass. In this case, and even when sorting 32-bit floating point numbers, radix sort can in practice be significantly faster than any other sorting algorithm. In one possible implementation of an LSD radix sort, variable length keys are padded with zero digits at the beginning of the keys to make all of the keys a fixed length, which requires O(NL) processing time, where N is the number of keys to be sorted and L is the length of the longest key. Big O notation or Big Oh notation, and also Landau notation or asymptotic notation, is a mathematical notation used to describe the asymptotic behavior of functions. ... Heapsort is one of the best general-purpose sort algorithms, and is part of the selection sort family. ... The integers are commonly denoted by the above symbol. ... A floating-point number is a digital representation for a number in a certain subset of the rational numbers, and is often used to approximate an arbitrary real number on a computer. ...

One disadvantage of an LSD radix sort is that it does not run in place, which means that the keys or pointers to the keys must be temporarily stored outside of their original memory space during processing. O(n) additional memory space is needed to hold the keys or pointers to the keys. For fixed-length keys, another disadvantage of an LSD radix sort is that it requires one sorting pass over the input list for each digit in a key. It has been suggested that Software pointer be merged into this article or section. ... It has been suggested that Software pointer be merged into this article or section. ...

An example

1. Original, unsorted list:

   170, 45, 75, 90, 2, 24, 802, 66

2. Sorting by least significant digit (1s place) gives:

   170, 90, 2, 802, 24, 45, 75, 66

   
   Notice that we keep 2 before 802, because 2 occurred before 802 in the original list, and similarly for 170 and 90.

3. Sorting by next digit (10s place) gives:

   2, 802, 24, 45, 66, 170, 75, 90

4. Sorting by most significant digit (100s place) gives:

   2, 24, 45, 66, 75, 90, 170, 802

It is important to realize that each of the above steps requires just a single pass over the data, since each item can be placed in its correct bucket without having to be compared with other items.

Some LSD radix sort implementations allocate space for buckets by first counting the number of keys that belong in each bucket before moving keys into those buckets. The number of times that each digit occurs is stored in an array. Consider the previous list of keys viewed in a different way: This article or section does not cite its references or sources. ...

170, 045, 075, 090, 002, 024, 802, 066

The first counting pass starts on the least significant digit of each key, producing an array of bucket sizes:

2 (bucket size for digits of 0: 170, 090)

2 (bucket size for digits of 2: 002, 802)

1 (bucket size for digits of 4: 024)

2 (bucket size for digits of 5: 045, 075)

1 (bucket size for digits of 6: 066)

A second counting pass on the next more significant digit of each key will produce an array of bucket sizes:

2 (bucket size for digits of 0: 002, 802)

1 (bucket size for digits of 2: 024)

1 (bucket size for digits of 4: 045)

1 (bucket size for digits of 6: 066)

2 (bucket size for digits of 7: 170, 075)

1 (bucket size for digits of 9: 090)

A third and final counting pass on the most significant digit of each key will produce an array of bucket sizes:

6 (bucket size for digits of 0: 002, 024, 045, 066, 075, 090)

1 (bucket size for digits of 1: 170)

1 (bucket size for digits of 8: 802)

At least one LSD radix sort implementation now counts the number of times that each digit occurs in each column for all columns in a single counting pass. (See the external links section.) Other LSD radix sort implementations allocate space for buckets dynamically as the space is needed. A radix sort is an algorithm that can rearrange integer representations based on the processing of individual digits in such a way that the integer representations are eventually in either ascending or descending order. ...

Iterative version using queues

A simple version of an LSD radix sort can be achieved using queues as buckets. The following process is repeated for a number of times equal to the length of the longest key: In providing services in computer science, transport, and operations research a queue (pronounced kyew) is a buffer where various entities such as data, objects, persons, or events are stored and waiting to be processed. ...

1. The integers are enqueued into an array of ten separate queues based on their digits from right to left. Computers often represent integers internally as fixed-length binary digits. Here, we will do something analogous with fixed-length decimal digits. So, using the numbers from the previous example, the queues for the 1st pass would be:

   0: 170, 090

   1: none

   2: 002, 802

   3: none

   4: 024

   5: 045, 075

   6: 066

   7 - 9: none

2. The queues are dequeued back into an array of integers, in increasing order. Using the same numbers, the array will look like this after the 1st pass:

   170, 090, 002, 802, 024, 045, 075, 066

3. For the second pass:

   Queues:

   0: 002, 802

   1: none

   2: 024

   3: none

   4: 045

   5: none

   6: 066

   7: 170, 075

   8: none

   9: 090

   Array:

   002, 802, 024, 045, 066, 170, 075, 090
   (note that at this point only 802 and 170 are out of order)

4. For the third pass:

   Queues:

   0: 002, 024, 045, 066, 075, 090

   1: 170

   2 - 7: none

   8: 802

   9: none

   Array:

   002, 024, 045, 066, 075, 090, 170, 802 (sorted)
   

While this may not be the most efficient radix sort algorithm, it is relatively simple, and still quite efficient.

Most significant digit radix sorts

A most significant digit (MSD) radix sort can be used to sort keys in lexicographic order. Unlike a least significant digit (LSD) radix sort, a most significant digit radix sort does not necessarily preserve the original order of duplicate keys. An MSD radix sort starts processing the keys from the most significant digit, leftmost digit, to the least significant digit, rightmost digit. This sequence is opposite that of least significant digit (LSD) radix sorts. An MSD radix sort stops rearranging the position of a key when the processing reaches a unique prefix of the key. Some MSD radix sorts use one level of buckets in which to group the keys. See the counting sort and pigeonhole sort articles. Other MSD radix sorts use multiple levels of buckets, which form a trie or a path in a trie. A postman's sort / postal sort is a kind of MSD radix sort. This article or section is not written in the formal tone expected of an encyclopedia article. ... In mathematics, the lexicographical order, or dictionary order, is a natural order structure of the cartesian product of two ordered sets. ... This article or section is not written in the formal tone expected of an encyclopedia article. ... This article or section is not written in the formal tone expected of an encyclopedia article. ... This article or section is not written in the formal tone expected of an encyclopedia article. ... Counting sort is a sorting algorithm which (like bucket sort) takes advantage of knowing the range of the numbers in the array to be sorted (array A). ... Pigeonhole sorting, also known as count sort, is a sorting algorithm that takes linear time (Θ(n)), which is the best possible performance for a sorting algorithm since one must inevitably look at each of the elements being sorted at least once, regardless of the sorting algorithm. ... Bucket sort is a sort algorithm that works by partitioning an array into a finite number of buckets and then sorting each bucket. ...

Recursion

A recursively subdividing MSD radix sort algorithm works as follows: A visual form of recursion known as the Droste effect. ...

1. Take the most significant digit of each key.
2. Sort the list of elements based on that digit, grouping elements with the same digit into one bucket.
3. Recursively sort each bucket, starting with the next digit to the right.
4. Concatenate the buckets together in order.

Implementation In computing, the term bucket can have several meanings. ... In formal language theory (and therefore in programming languages), concatenation is the operation of joining two character strings end to end. ...

A two pass method can be used to first find out how big each bucket needs to be and then place each key (or pointer to the key) into the appropriate bucket. A single pass system can also be used, where each bucket is dynamically allocated and resized as needed, but this runs the risk of serious memory fragmentation, discontiguous allocations of memory, which may degrade performance. This memory fragmentation could be avoided if a fixed allocation of buckets is used for all possible values of a digit, but, for an 8 bit digit, this would require 256 (2⁸) buckets, even if not all of the buckets were used. So, this approach might use up all available memory quickly and go into paging space, where data is stored and accessed on a hard drive or some other secondary memory device instead of main memory, which would radically degrade performance. A fixed allocation approach would only make sense if each digit was very small, such as a single bit.

Application to parallel computing

Note that this recursive sorting algorithm has particular application to parallel computing, as each of the subdivisions can be sorted independently of the rest. In this case, each recursion is passed to the next available processor. A single processor would be used at the start (the most significant digit). Then, by the second or third digit, all available processors would likely be engaged. Ideally, as each subdivision is fully sorted, fewer and fewer processors would be utilized. In the worst case, all of the keys will be identical or nearly identical to each other, with the result that there will be little to no advantage to using parallel computing to sort the keys. Parallel computing is the simultaneous execution of the same task (split up and specially adapted) on multiple processors in order to obtain results faster. ...

A recursive forward radix sort example

Sort the list:
170, 045, 075, 090, 002, 024, 802, 066

1. Sorting by most significant digit (100s place) gives:
   Zero hundreds bucket: 045, 075, 090, 002, 024, 066
   One hundreds bucket: 170
   Eight hundreds bucket: 802
2. Sorting by next digit (10s place) is only needed for those numbers in the zero hundreds bucket (no other buckets contain more than one item):
   Zero tens bucket: 002
   Twenties bucket: 024
   Forties bucket: 045
   Sixties bucket: 066
   Seventies bucket: 075
   Nineties bucket: 090
3. Sorting by least significant digit (1s place) is not needed, as there is no tens bucket with more than one number. Therefore, the now sorted zero hundreds bucket is concatenated, joined in sequence, with the one hundreds bucket and eight hundreds bucket to give:
   002, 024, 045, 066, 075, 090, 170, 802

This example used base ten digits for the sake of readability, but of course binary digits or perhaps bytes might make more sense for a binary computer to process. In mathematics, the base or radix is the number of various unique symbols (digits), including zero, that a positional numeral system uses to represent numbers in a given counting system. ... In computer science a byte is a unit of measurement of information storage, most often consisting of eight bits. ...

Efficiency

The MSD recursive radix sort is the most efficient when most rows only need to be sorted a few digits deep. In this case, only a few digits need to be processed, versus all digits in the key by the nonrecursive LSD radix sort. On the other hand, if most rows need to be sorted to the last significant digit in each key (such as when many rows have duplicate keys) then the overhead of passing data to each recursion of the program increases processing time relative to the nonrecursive LSD radix sort, which should be used for such cases.

Neither version of the radix sort is very efficient when the data is almost completely sorted to begin with, since they would both ignore this fact and sort all the data again. However, the completely sorted case can be easily detected in the first pass through the data when determining the sizes of the buckets.

Incremental trie-based radix sort

Another way to proceed with an MSD radix sort is to use more memory to create a trie to represent the keys and then traverse the trie to visit each key in order. A depth-first traversal of a trie starting from the root node will visit each key in order. A depth-first traversal of a trie, or any other kind of acyclic tree structure, is equivalent to traversing a maze via the right-hand rule. A trie for keys to, tea, ten, i, in, and inn. In computer science, a trie, or prefix tree, is an ordered tree data structure that is used to store an associative array where the keys are usually strings. ... A trie for keys to, tea, ten, i, in, and inn. In computer science, a trie, or prefix tree, is an ordered tree data structure that is used to store an associative array where the keys are usually strings. ... Depth-first search (DFS) is an algorithm for traversing or searching a tree, tree structure, or graph. ... A trie for keys to, tea, ten, i, in, and inn. In computer science, a trie, or prefix tree, is an ordered tree data structure that is used to store an associative array where the keys are usually strings. ... A root node is a specially chosen node in a tree data structure at which all operations on the tree begin. ... Depth-first search (DFS) is an algorithm for traversing or searching a tree, tree structure, or graph. ... A trie for keys to, tea, ten, i, in, and inn. In computer science, a trie, or prefix tree, is an ordered tree data structure that is used to store an associative array where the keys are usually strings. ... Acyclic can mean any of the following: In chemistry, an acyclic compound is a hydrocarbon compound having an open chain. ... A small maze. ...

A trie essentially represents a set of strings or numbers, and a radix sort which uses a trie structure is not necessarily stable, which means that the original order of duplicate keys is not necessarily preserved, because a set does not contain duplicate elements. Additional information will have to be associated with each key to indicate the population count or original order of any duplicate keys in a trie-based radix sort if keeping track of that information is important for a particular application. It may even be desirable to discard any duplicate strings as the trie creation proceeds if the goal is to find only unique strings in sorted order. Some people sort a list of strings first and then make a separate pass through the sorted list to discard duplicate strings, which can be slower than using a trie to simultaneously sort and discard duplicate strings in one pass. In mathematics, a set can be thought of as any collection of distinct objects considered as a whole. ...

One of the advantages of maintaining the trie structure is that the trie makes it possible to determine quickly if a particular key is a member of the set of keys in a time that is proportional to the length of the key, k, in O(k) time, that is independent of the total number of keys. Determining set membership in a plain list, as opposed to determining set membership in a trie, requires binary search, O(k*log(n)) time; linear search, O(kn) time; or some other method whose execution time is in some way dependent on the total number, n, of all of the keys in the worst case. It is sometimes possible to determine set membership in a plain list in O(k) time, in a time that is independent of the total number of keys, such as when the list is known to be in an arithmetic sequence or some other computable sequence. In computer science, binary search or binary chop is a search algorithm for finding a particular value in a linear array, by ruling out half of the data at each step. ... In computer science, linear search is a search algorithm, also known as sequential search, that is suitable for searching a set of data for a particular value. ... This is a page about mathematics. ...

Maintaining the trie structure also makes it possible to insert new keys into the set incrementally or delete keys from the set incrementally while maintaining sorted order in O(k) time, in a time that is independent of the total number of keys. In contrast, other radix sorting algorithms must, in the worst case, re-sort the entire list of keys each time that a new key is added or deleted from an existing list, requiring O(kn) time.

Snow White analogy

If the nodes were rooms connected by hallways, then here is how a woman named Snow White might proceed to visit all of the dwarfs if the place were dark, keeping her right hand on a wall at all times: Image File history File links 7dwarves. ...

1. She travels down hall B to find Bashful. She asks him where the other dwarfs are, but he is too shy to say anything.
2. She continues moving forward with her right hand on the wall, because it is dark, which takes her around the room and back up hall B.
3. She moves down halls D, O, and C to find Doc who is too busy with reading a book by a candle to help her find the other dwarfs.
4. Continuing to follow the wall with her right hand, she goes back up hall C, then down hall P.
5. She finds Dopey, but he just shrugs when she asks him where the other dwarfs are.
6. She continues back up halls P, O, D, and then goes down hall G to find Grumpy, who is too grumpy to help her.
7. She continues back up hall G, with her right hand still on the wall, and goes down hall H to the room where Happy is. He is happy to see her but does not know where the other dwarfs are.
8. She travels back up hall H and turns right down halls S and L, where she finds Sleepy, who is sleeping.
9. She goes back up hall L (with her right hand still on the wall), down hall N, where she finally finds Sneezy.
10. She travels back up halls N and S to her starting point and knows that she is done.

These series of steps serve to illustrate the path taken in the trie by Snow White via a depth-first traversal to visit the dwarfs by the ascending order of their names, Bashful, Doc, Dopey, Grumpy, Happy, Sleepy, and Sneezy. The algorithm for performing some operation on the data associated with each node of a tree first, such as printing the data, and then moving deeper into the tree is called a pre-order traversal, which is a kind of depth-first traversal. A pre-order traversal is used to process the contents of a trie in ascending order. If Snow White wanted to visit the dwarfs by the descending order of their names, then she could walk backwards while following the wall with her right hand, or, alternatively, walk forward while following the wall with her left hand. The algorithm for moving deeper into a tree first until no further descent to unvisited nodes is possible and then performing some operation on the data associated with each node is called post-order traversal, which is another kind of depth-first traversal. A post-order traversal is used to process the contents of a trie in descending order. Depth-first search (DFS) is an algorithm for traversing or searching a tree, tree structure, or graph. ... In computer science, tree traversal is the process of visiting each node in a tree data structure. ... Depth-first search (DFS) is an algorithm for traversing or searching a tree, tree structure, or graph. ... In computer science, tree traversal is the process of visiting each node in a tree data structure. ... In computer science, tree traversal is the process of visiting each node in a tree data structure. ... Depth-first search (DFS) is an algorithm for traversing or searching a tree, tree structure, or graph. ... In computer science, tree traversal is the process of visiting each node in a tree data structure. ...

The root node of the trie in the diagram essentially represents a null string, an empty string, which can be useful for keeping track of the number of blank lines in a list of words. The null string can be associated with a circularly linked list with the null string initially as its only member, with the forward and backward pointers both initially pointing to the null string. The circularly linked list can then be expanded as each new key is inserted into the trie. The circularly linked list is represented in the following diagram as thick, grey, horizontally linked lines: A root node is a specially chosen node in a tree data structure at which all operations on the tree begin. ... A trie for keys to, tea, ten, i, in, and inn. In computer science, a trie, or prefix tree, is an ordered tree data structure that is used to store an associative array where the keys are usually strings. ... In computer science, a linked list is one of the fundamental data structures used in computer programming. ... In computer science, a linked list is one of the fundamental data structures used in computer programming. ... A trie for keys to, tea, ten, i, in, and inn. In computer science, a trie, or prefix tree, is an ordered tree data structure that is used to store an associative array where the keys are usually strings. ... In computer science, a linked list is one of the fundamental data structures used in computer programming. ...

If a new key, other than the null string, is inserted into a leaf node of the trie, then the computer can go to the last preceding node where there was a key or a bifurcation to perform a depth-first search to find the lexicographic successor or predecessor of the inserted key for the purpose of splicing the new key into the circularly linked list. The last preceding node where there was a key or a bifurcation, a fork in the path, is a parent node in the type of trie shown here, where only unique string prefixes are represented as paths in the trie. If there is already a key associated with the parent node that would have been visited during a movement away from the root during a right-hand, forward-moving, depth first traversal, then that immediately ends the depth-first search, as that key is the predecessor of the inserted key. For example, if Bashful is inserted into the trie, then the predecessor is the null string in the parent node, which is the root node in this case. In other words, if the key that is being inserted is on the leftmost branch of the parent node, then any string contained in the parent node is the lexicographic predecessor of the key that is being inserted, else the lexicographic predecessor of the key that is being inserted exists down the parent node's branch that is immediately to the left of the branch where the new key is being inserted. For example, if Grumpy were the last key inserted into the trie, then the computer would have a choice of trying to find either the predecessor, Dopey, or the successor, Happy, with a depth-first search starting from the parent node of Grumpy. With no additional information to indicate which path is longer, the computer might traverse the longer path, D, O, P. If Dopey were the last key inserted into the trie, then the depth-first search starting from the parent node of Dopey would soon find the predecessor, Doc, because that would be the only choice. Image File history File links 7DwarfsThreaded. ... 9, 14, 19, 67 and 76 are leaf nodes. ... A trie for keys to, tea, ten, i, in, and inn. In computer science, a trie, or prefix tree, is an ordered tree data structure that is used to store an associative array where the keys are usually strings. ... Depth-first search (DFS) is an algorithm for traversing or searching a tree, tree structure, or graph. ... In computer science, a linked list is one of the fundamental data structures used in computer programming. ... A parent node (or ancestor node) is a node in a tree data structure that links to one or more child nodes. ... A parent node (or ancestor node) is a node in a tree data structure that links to one or more child nodes. ... Depth-first search (DFS) is an algorithm for traversing or searching a tree, tree structure, or graph. ... A parent node (or ancestor node) is a node in a tree data structure that links to one or more child nodes. ... A root node is a specially chosen node in a tree data structure at which all operations on the tree begin. ... A parent node (or ancestor node) is a node in a tree data structure that links to one or more child nodes. ... A parent node (or ancestor node) is a node in a tree data structure that links to one or more child nodes. ... Depth-first search (DFS) is an algorithm for traversing or searching a tree, tree structure, or graph. ... Depth-first search (DFS) is an algorithm for traversing or searching a tree, tree structure, or graph. ...

If a new key is inserted into an internal node, then a depth-first search can be started from the internal node to find the lexicographic successor. For example, if the literal string, "DO", were inserted in the node at the end of the path D, O, then a depth-first search could be started from that internal node to find the successor, "DOC", for the purpose of splicing the new string into the circularly linked list. In computer science, an internal node or inner node is any node of a tree data structure that is not a leaf node. ... Depth-first search (DFS) is an algorithm for traversing or searching a tree, tree structure, or graph. ... In computer science, an internal node or inner node is any node of a tree data structure that is not a leaf node. ... Depth-first search (DFS) is an algorithm for traversing or searching a tree, tree structure, or graph. ... In computer science, an internal node or inner node is any node of a tree data structure that is not a leaf node. ... In computer science, a linked list is one of the fundamental data structures used in computer programming. ...

Forming the circularly linked list requires more memory but allows the keys to be visited more directly in either ascending or descending order via a linear traversal of the linked list rather than a depth-first traversal of the entire trie. This concept of a circularly linked trie structure is similar to the concept of a threaded binary tree. Let's call this structure a circularly threaded trie. In computer science, a linked list is one of the fundamental data structures used in computer programming. ... Depth-first search (DFS) is an algorithm for traversing or searching a tree, tree structure, or graph. ... A threaded binary tree may be defined as follows: A binary tree is threaded by making all right child pointers that would normally be null point to the inorder successor of the node, and all left child pointers that would normally be null point to the inorder predecessor of the...

When a trie is used to sort numbers, the number representations must all be the same length unless you are willing to perform a breadth-first traversal. When the number representations will be visited via depth-first traversal, as in the above diagram, the number representations will always be on the leaf nodes of the trie. Note how similar in concept this particular example of a trie is to the recursive forward radix sort example which involves the use of buckets instead of a trie. Performing a radix sort with the buckets is like creating a trie and then discarding the non-leaf nodes. Image File history File links Trie002. ... A trie for keys to, tea, ten, i, in, and inn. In computer science, a trie, or prefix tree, is an ordered tree data structure that is used to store an associative array where the keys are usually strings. ... In graph theory, breadth-first search (BFS) is a graph search algorithm that begins at the root node and explores all the neighboring nodes. ... Depth-first search (DFS) is an algorithm for traversing or searching a tree, tree structure, or graph. ... 9, 14, 19, 67 and 76 are leaf nodes. ... A trie for keys to, tea, ten, i, in, and inn. In computer science, a trie, or prefix tree, is an ordered tree data structure that is used to store an associative array where the keys are usually strings. ... A radix sort is an algorithm that can rearrange integer representations based on the processing of individual digits in such a way that the integer representations are eventually in either ascending or descending order. ...

Sample implementations

C# least significant digit (LSD) radix sort implementation

Here we sort an integer array that's passed to the RadixSort method (Note: all arrays in C#/.NET are reference types, and therefore a is a reference to an array). C# (pronounced see-sharp) is an object-oriented programming language developed by Microsoft as part of their . ...

 public void RadixSort(int[] a) { // our helper array int[] t=new int[a.Length]; // number of bits our group will be long int r=4; // try to set this also to 2, 8 or 16 to see if it is quicker or not // number of bits of a C# int int b=32; // counting and prefix arrays (note dimensions 2^r which is the number of all possible values of a r-bit number) int[] count=new int[1<<r]; int[] pref=new int[1<<r]; // number of groups int groups=(int)Math.Ceiling((double)b/(double)r); // the mask to identify groups int mask = (1<<r)-1; // the algorithm: for (int c=0, shift=0; c<groups; c++, shift+=r) { // reset count array for (int j=0; j<count.Length; j++) count[j]=0; // counting elements of the c-th group for (int i=0; i<a.Length; i++) count[(a[i]>>shift)&mask]++; // calculating prefixes pref[0]=0; for (int i=1; i<count.Length; i++) pref[i]=pref[i-1]+count[i-1]; // from a[] to t[] elements ordered by c-th group for (int i=0; i<a.Length; i++) t[pref[(a[i]>>shift)&mask]++]=a[i]; // a[]=t[] and start again until the last group t.CopyTo(a,0); } // a is sorted } 

C++ LSD radix sort example of non-recursive implementation

 // C++ LSD Radix Sort example, queue implementation #include <iostream> #include <cstdlib> #include <ctime> using std::cout; // Remove this line for older C++ compilers typedef struct slist_ { int val; struct slist_ *next; } slist; slist *radixsort(slist *L, int t) { int i, j, d, m=1; slist *temp, *head[10], *tail[10]; // Process t digits for (j=1; j<=t; j++) { // Initialize the queues, 0 to 9 for (i=0; i<=9; i++) { head[i] = NULL; tail[i] = NULL; } // Process the list L while ( L != NULL ) { // Get the decimal digit with place value m d = ((int)(L->val/m))%10; // Make temp point to the current list item temp = L; // Make L point to the next list item L = L->next; // Disconnect the current list item, making it self-contained temp->next = NULL; if (head[d]!= NULL) { // The queue for digit d is not empty // Add the list item to the end of the queue for digit d tail[d]->next = temp; // Make tail[d] point to the new tail item of queue d tail[d] = temp; } else { // The queue for digit d is empty head[d] = temp; // Point to the new head tail[d] = temp; // Point to the new tail } } // while // Find the index, d, of the first non-empty queue d=0; while (head[d]==NULL) d++; // Point to the first item of the first non-empty queue L = head[d]; // Point to the last item of the first non-empty queue temp = tail[d]; // Append the items of the remaining non-empty queues // to the tail of list L. d++; while (d<10) { if (head[d]!=NULL) { // Append the items of non-empty queue d to list L temp->next = head[d]; // Point to the new tail of list L temp = tail[d]; } d++; } // while // Prepare to process the next more significant digit m = m*10; } // for return L; } int main() { // Initialize the random number seed with the time srand( (unsigned int)time(NULL) ); int i,size=20, *n, max=-1, t=0; // Generate some random numbers n = new int[size]; slist *start=NULL,*end=NULL,*temp; for (i=0; i<size; i++) { n[i] = rand(); } // Find the largest value and create a linked list of the random values for (i=0; i<size; i++) { // Find the largest value if (n[i] > max) max = n[i]; // Create a new node temp = new slist; // Fill the node with a random value temp->val = n[i]; // Seal the node temp->next = NULL; if (start != NULL) { // Append the new node to the linked list end->next = temp; end = temp; } else { // Add the first node to the linked list start = temp; end = temp; } } // Find the number of decimal digits in the largest random value while (max>0) { t=t+1; max=max/10; } // Perform the radix sort start = radixsort(start, t); // Display the results cout << "after radix sort.n"; temp = start; for (i=0; i<size; i++) { cout << temp->val << "n"; temp = temp->next; } // Return a zero to the calling script, batch file, or command shell // to indicate successful completion. return 0; } // main  

C++ (pronounced see plus plus, IPA: ) is a general-purpose, high-level programming language with low-level facilities. ...

C sample MSD implementation

 /* Note: Because of the constant cost per iteration (Running through 3 loops 256 times), * using a simpler in place sort routine when the size of the array is small enough * is generally a good idea. This code handles duplicate entries without any problems. */ void sortsub(unsigned char **data, unsigned int len, int offset) { unsigned int counts[2][256]; unsigned int i, currentKey, start; for (i=0; i<256; i++) counts[0][i] = 0; for (i=0; i<len; i++) { counts[0][data[i][offset]]++; } counts[1][0] = counts[0][0]; for (i=1; i<256; i++) { counts[1][i] = (counts[0][i] += counts[0][i-1]); } currentKey = 0; start = 0; i = 0; while (1) { if (counts[1][currentKey] <= i) { if (currentKey && start + 1 < counts[0][currentKey]) { sortsub(data+counts[0][currentKey-1], counts[0][currentKey]-counts[0][currentKey-1], offset+1); } if (currentKey == 255) break; start = i = counts[0][currentKey++]; } else { unsigned char key = data[i][offset]; if (key == currentKey) i++; else { unsigned char *temp = data[--counts[1][key]]; data[counts[1][key]] = data[i]; data[i] = temp; } } } } void sort (unsigned char **data, unsigned int len) { sortsub(data, len, 0); }  

C is a general-purpose, procedural, imperative computer programming language developed in 1972 by Dennis Ritchie at the Bell Telephone Laboratories for use with the Unix operating system. ...

See also

• IBM 80 series Card Sorters

Later model IBM card sorter, type 84 The IBM 80 Electric Punched Card Sorting Machine, was introduced by IBM in 1925. ...

External links

• Demonstration and comparison of Radix sort with Bubble sort, Merge sort and Quicksort implemented in JavaScript
• Page with visual demonstrations of sorting algorithms including Radix sort, all implemented in Java.
• Article about Radix sorting IEEE floating-point numbers with implementation. Note: Individual hexadecimal digits represent 4 bits, not the 8 bits that the author of the article indicates. Pairs of hexadecimal digits, such as 8A, represent 8 bits.

  Faster Floating Point Sorting and Multiple Histogramming with implementation in C++

• Pointers to radix sort visualizations

Bubble sort, sometimes shortened to bubblesort, is a simple sorting algorithm. ... A merge sort algorithm used to sort an array of 7 integer values. ... Quicksort in action on a list of random numbers. ... JavaScript is the name of Netscape Communications Corporations and now the Mozilla Foundations implementation of the ECMAScript standard, a scripting language based on the concept of prototype-based programming. ... Java is an object-oriented applications programming language developed by Sun Microsystems in the early 1990s. ... The IEEE Standard for Binary Floating-Point Arithmetic (IEEE 754) is the most widely-used standard for floating-point computation, and is followed by many CPU and FPU implementations. ... In mathematics and computer science, hexadecimal, base-16, or simply hex, is a numeral system with a radix, or base, of 16, usually written using the symbols 0–9 and A–F, or a–f. ... In mathematics and computer science, hexadecimal, base-16, or simply hex, is a numeral system with a radix, or base, of 16, usually written using the symbols 0–9 and A–F, or a–f. ...

References

• Donald Knuth. The Art of Computer Programming, Volume 3: Sorting and Searching, Third Edition. Addison-Wesley, 1997. ISBN 0-201-89685-0. Section 5.2.5: Sorting by Distribution, pp.168–179.
• Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms, Second Edition. MIT Press and McGraw-Hill, 2001. ISBN 0-262-03293-7. Section 8.3: Radix sort, pp.170–173.
• BRADSORT v1.50 source code
• Efficient Trie-Based Sorting of Large Sets of Strings, by Ranjan Sinha and Justin Zobel. This paper describes a method of creating tries of buckets which figuratively burst into sub-tries when the buckets hold more than a predetermined capacity of strings, hence the name, "Burstsort."