Analysis Criteria for Sorting Algorithms

There are few sorting algorithms namely bubble sort, selection sort, insertion sort, merge sort etc which every coder must know. But what do you think makes these sorting algorithms different from each other? There are few analysis criteria which makes these algorithms stand out from each other. Let's see what are those-

1. Time Complexity-

The amount of time an algorithm takes to solve maximum number of inputs. It is the amount of time taken by an algorithm to run, as a function of the length of the input n and is represented using Big-O notation. n indicates the input size, while O is the worst-case scenario growth rate function.

As the total time taken can vary based on various factors(Ex. Processor speed , temperature, No. of concurrent tasks running in memory etc.), we use number of operations performed to find the time complexity. This helps in estimating the performance of a program irrespective of the kind of machine it runs on. Quick sort are Merge sort are some of the best algorithms in terms of average time complexity.

2. Space Complexity-

The amount of space an algorithm takes to solve a problem. The less space it takes, better the algorithms will be. It includes both the space used by input and the temporary space (Auxiliary space) taken during execution of a program.

Inplace sorting algorithm - If your algorithm takes a constant memory, then it is called as inplace sorting algorithm. It means that if the algorithm takes an input array of size 10 or 100, and the memory optimised is still the same and is not growing with the array size, it is known as inplace sorting algorithm. Few example of Inplace sorting algorithms are Bubble sort, insertion sort etc. On the other hand Merge sort is not- in place sorting algorithms.

3. Stability -

If you are sorting an array, and the order of same elements in output and input array does not change, then it is known as the stable algorithm. In other words, it means that the relative positions of equivalent elements remain same. For example, Merge sort which maintains the order of original data in case of equivalent elements and it is an example of stable algorithm.

4. Internal and External sorting algorithms-

Internal SA- All the data is loaded into the memory i.e. the entire sorting can be done in the main memory. External SA- All the data is not loaded into the memory i.e. sorts cannot be done in the main memory and must be done on disk or tape. External sorting is used for very large amount of data.

5. Adaptive-

Adaptive algorithm means that if the input array is already sorted, it takes less time. Adaptive algorithms are better than non-adaptive algorithms. For example, when an array is almost sorted it is best to use insertion sort algorithm.

6. Recursive/Non-Recursive sorting algorithms-

Recursive algorithm uses recursion i.e. it calls itself to sort a small part of the array and combines all the sorted parts to form the complete sorted array. While Non-Recursive sorting algorithms does not uses recursion and sorts the complete without dividing the array. Merge sort and Quick sort are examples of Recursive Algorithms

Here, time and space complexity criteria can be used to compare all the algorithms but others are used only for sorting algorithms.