Radix sort

RADIX SORT:

Definition:

Radix sort is a non-comparative integer sorting algorithm that sorts data with integer keys by grouping keys by the individual digits which share the same significant position and value 

·        sort by the least significant digit first (counting sort)

Numbers with the same digit go to same bin

o  reorder all the numbers: the numbers in bin 0 precede the numbers in bin 1, which precede the numbers in bin 2, and so on

o  sort by the next least significant digit

o  continue this process until the numbers have been sorted on all k digits

Algorithm:

Extra information: every integer can be represented by at most k digits 

o d1d2…dk where di are digits in base r

o d1: most significant digit 

o dk: least significant digit

Example: 275, 087, 426, 061, 509, 170, 677, 503

Complexity Analysis:

k passes over the numbers (i.e. k counting sorts, with range being 0..r) 

each pass takes O(N+r)

total: O(Nk+rk)

r and k are constants: O(N)

MERGE SORT

Definition;

The Merge sort algorithm is based on divide and conquers strategy. First, the sequence to be sorted is decomposed into two halves ( Divide ). Each half is sorted independently ( Conquer ). Then the two sorted halves are merged to a sorted sequence ( Combine ).