## Comparison of Sorting Algorithms

In this blog, we will analyze and compare different sorting algorithms on the basis of different parameters like Time Complexity, In-place, Stability, etc.

**Comparison based sorting algorithms **

- In a comparison based sorting algorithms, we compare elements of an array with each other to determines which of two elements should occur first in the final sorted list.
- All comparison-based sorting algorithms have a complexity lower bound of
**nlogn. (Think!)** - Here is the comparison of time and space complexities of some popular comparison based sorting algorithms:

**Non-comparison based sorting algorithm**

- There are sorting algorithms that use special information about the keys and operations other than comparison to determine the sorted order of elements.
- Consequently,
**nlogn**lower bound does not apply to these sorting algorithms.

#### In-place and Stable sorting Algorithms

- A sorting algorithm is
**In-place**if the algorithm does not use extra space for manipulating the input but may require a small though nonconstant extra space for its operation. Or we can say, a sorting algorithm sorts in-place if only a constant number of elements of the input array are ever stored outside the array. - A sorting algorithm is
**stable**if it does not change the order of elements with the same value.

Online/Offline:The algorithm that accepts a new element while the sorting process is going on, that algorithm is called the online sorting algorithm. From, the above sorting algorithms, the insertion sort is online.

#### Critical ideas to think

- Understanding the sorting algorithms are the best way to learn problem solving and complexity analysis in the algorithms. In some cases, We often use sorting as a key routine to solve several coding problems.
- Knowing which algorithm is best possible depends heavily on details of the application and implementation. In most practical situations, quicksort is a popular algorithm for sorting large input arrays because its expected running time is O(nlogn). It also outperforms heap sort in practice.
- If stability is important and space is available, the merge sort might be the best choice for the implementation.
**(Think!)** - Like insertion sort, quick sort has tight code and hidden constant factor in its running time is small.
- When the input array is almost sorted or input size is small, then the insertion sort can be preferred.
- We can prefer merge sort for sorting a linked list.
**(Think!)**

**Suggested problems to solve**

- Bubble Sort
- Selection Sort
- Insertion Sort
- Quick Sort
- Merge Sort
- Heap Sort
- Find the intersection of two unsorted arrays
- Find whether an array is a subset of another array
- Remove duplicates from an unsorted array
- Find the most frequent element in an array
- Check for pair in an array with a given sum

**Happy Coding, Enjoy Algorithms!**