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
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
k passes over the numbers (i.e. k counting sorts, with range being 0..r)
each pass takes O(N+r)
r and k are constants: O(N)
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 ).
Copyright © 2018-2020 BrainKart.com; All Rights Reserved. Developed by Therithal info, Chennai.