Getting Started With Sorting

In this series of blog post we are going to understand various approaches for sorting a set of numbers. Given an input of numbers we are going to display the output of numbers in ascending or descending order using various algorithms. In this series we will be dealing with the following algorithms:

• Insertion Sort
• Merge Sort
• Heap Sort
• Quick Sort
• Bucket Sort
• Radix Sort </ul> </p>

  Each of the above algorithm solves the following problem:

  Input: A sequence of n numbers arranged in random manner (n1,n2,n5,n3…..n100)

  Output: Reordering of numbers in ascending or descending order (n1,n2,n3…n100)

  For solving the above data structure we generally use arrays, but some of the algorithms will use linked list or trees to make it easier and effective to solve sorting problems.

  Why algorithm to use and when ?

  By going through the above links we have a fair understanding of sorting algorithms. The worst case of insertion sort is theta(n*n). Inner loop are being accessed frequently making it asymptotically weak when we have a large number of elements to consider. However if number of elements are small it’s a fast sorting algorithm.

  Next we have merge sort which has fairly better asymptotic running time of theta(n lgn), but the merge procedure it uses does not operate in every place.

  Next we have heap sort which sorts n random numbers in O(n lgn) time. It uses an important data structure called heap.

  Next we have quick sort which is also used to sort n numbers but its worst-case running time is theta(n*n), however its expected running time is theta(n lgn).Like insertion sort it has a hidden constant factor in its running time. It’s a popular algorithm for sorting large input arrays. Insertion sort, merge sort, heap sort and quick sort all of the mentioned algorithm are comparison algorithm. Further we will study bucket sort and radix sort which sorts on the basis of the index instead of comparing element with each other, such type of algorithm takes linear time to sort elements. Finally we’ll have a look at all the algorithms with their worst case and average case running time.

  Algorithm	Worst-case Running Time	Average-case Running Time
  Insertion Sort	θ (n*n)	θ (n*n)
  Merge Sort	θ (n*lgn)	θ (n*lgn)
  Heap Sort	O(n*lgn)	-
  Quick Sort	θ(n*n)	θ(n*lgn)
  Counting Sort	θ(k+n)	θ(k+n)
  Radix Sort	θ(d(n+k))	θ(d(n+k))
  Bucket Sort	θ(n*n)	θ(n)