Home | | **Fundamentals of Data Structures in C** | | **Data Structures** | | **Programming and Data Structures I** | Radix sort

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

**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 (

Study Material, Lecturing Notes, Assignment, Reference, Wiki description explanation, brief detail

**Related Topics **

Copyright © 2018-2020 BrainKart.com; All Rights Reserved. Developed by Therithal info, Chennai.