Sorting is one of the major problems in Computer Science and Engineering. One needs to sort data in an ascending or a descending order based on problem statement. Efficient sorting is required to optimize the performance of other algorithms such as searching and merging. There are two types of sorting methods viz. Comparison Based Sorting and Non-comparison Based Sorting. In Comparison Based Sorting methods, elements are compared with each other to get the sorted order. In Non-comparison Based Sorting methods, elements are not compared with each other to get sorted order. Bubble Sort, Insertion Sort, Selection Sort, Merge Sort, Quick Sort, Heap Sort, and Shell Sort are examples of Comparison Based Sorting methods whereas Radix Sort, Count Sort, and Bucket Sort are examples of Non-comparison Based Sorting methods.

Worst case time complexity of Bubble Sort is O (n²), where n indicates the number of elements to be sorted. It is applicable to small size data and usually is not used to solve problems in real-world applications. The best case and worst case time complexities of Insertion Sort are Ω (n) and O (n²) respectively.  These are used in situations when the data to be sorted is small in size and is almost in a sorted order. The best case and worst case time complexities of Selection Sort are Ω (n²) and O (n²) respectively. These too are used when the data size is small. The space complexity of all the above sorting methods is equal to O (1), as these methods don’t require additional memory to get sorted order data. One can choose the above sorting methods when memory requirement is very high.

Merge Sort, Quick Sort, and Heap Sort are efficient sorting methods wherein time complexity is less. Among these sorting methods, Quick Sort is the fastest sorting method but its worst case time complexity is O (n²). Merge Sort and Heap Sort give O (nlogn) time complexity in all cases, i.e., best case, average case, and worst case. Quick Sort is preferred over Merge and Heap Sort if the researcher or developer is confident about balanced partitioning of the data.

Merge Sort is applicable in situations, when data size is very large and is unable to fit in a computer’s main memory like RAM although its space complexity is O (n). If there is a high requirement of memory and one wants to find the smallest or the largest element quickly, Heap Sort is preferred because its space complexity is O (1).

Radix Sort or Bucket Sort is specially used to sort out fixed size integers, fixed size strings and floating points of certain range and leads to worst case time complexity of O (d*(n+b)), where d is number of digits required to represent maximum number from the list, n indicates number of elements to be sorted and b indicates number of buckets required to sort out elements. For integers b=10, as there are 10 digits and for strings b=26, as there are 26 alphabets.

Counting Sort is one of the non-comparison based sorting methods, which runs in linear time, i.e., O (n+k), where n shows number of elements to be sorted and k is the maximum element. It is used when the range of the values is small and the list contains duplicate entries of the elements.

The author of this article is Prof. Ajitkumar Shitole with the Department of Computer Engineering at International Institute of Information Technology, I²IT, Pune