Sorting in Linear Time in data Structure

Sorting in linear time algorithm run faster than the comparison based sorting algorithm . But they require special assumption about input sequence . This Algorithm use operations other than comparison to determine the sorted order.

Types of Linear Time Sorting Algorithm

Counting Sort: Counting Sort assumes that the input consists of integers in a small range.

Radix Sort: It is a sorting algorithm that sort integer by processing individual digits by comparing individual digits sharing the same significant position.

Bucket Sort: Bucket sort assumes that the input is generated by a random process that distribution elements uniformly over the interval U={0,1}

Disadvantage of Sorting In Linear Time Algorithm:

• Despite of Linear Time usually these algorithm are not very desirable form practical point of view their are some shortcoming like
  • The efficiency of these algorithm depends on the keys randomly ordered.
  • If this condition is not satisfied then result may lead to degrade in the performance.
• These Algorithm require extra space proportional to the size of the array being sorted.
• The inner loop of these Algorithm contains a few instructions.
• So, even though they are linear they would not be as faster than quick sort.