Data Structures/merge Sort

From Wikibooks, the open-content textbooks collection

A Wikibookian suggests that this book or chapter be merged into Algorithms. Please discuss whether or not this merge should happen on the discussion page.

Radix Sort is a sorting algorithm designed to work on items where the key of each item is an ordered set of integers in the range 0 to (N-1) inclusive both ends, or can be transformed into such an ordered set.

[edit] Key Comparing

Keys are compared in the following way: Let k_a be the key of the one item, called item A, let k_b be the key of the other item, called item B. Let k_a(i) be the i^th entry in the key k_a, where the first entry is at index 0. Let i = 0. If the keys are less than i elements long then the keys are equal. If k_a(i) < k_b(i), then item A is ordered before item B. If k_a(i) > k_b(i), then item B is ordered before item A. If k_a(i) = k_b(i), then add one to i, and return the line under "Let i = 0."

[edit] Sorting Algorithm

You start with an unordered sequence. You create N empty queues. You loop over every item to be sorted. On each loop iteration, you look at the last element in the key. You move that item into the end of the queue which corresponds to that element. When you are finished looping you concatenate all the queues together into another sequence. You then reapply the procedure described but look at the second last element in the key. You keep doing this until you have looped over every key. When you complete this process the resulting sequence will be sorted as described above.

A reader has identified this page or section as an undeveloped draft or outline. You can help to develop the work, or you can ask for assistance in the project room.

[edit] Time Cost

Let n_i be the number of items in the sequence to be sorted. N is number of integers that each key element can take. Let n_k be the number of keys in each item.

The total time to sort the sequence is thus O(n_k(n_i + N)).

See also: Bubble Sort.