# Best Sorting Algorithm

## Introduction

We have often felt the need to sort our data. Whether it be it a list, array, or any collection, the very first problem we face is choosing the right sorting algorithm. Since there are many different sorting techniques/algorithms and some algorithms are better than the others, there is no best sorting algorithm, it depends on the data/situation. Before looking at when to use each sorting algorithm, let's look at the factors which help us to determine a good sorting algorithm.

## Time/Time Complexity

This factor helps us to know how much fast is an algorithm? And this factor has 3 major scenarios, firstly is when the data is sorted beforehand, which means no swaps are needed, it only checks the order of the data. This is known as a best-case scenario. The second scenario, the worst-case scenario, is when the algorithm needs to perform maximum swapping in order to sort the data. The last scenario is when the number of swapping lies between 0 to maximum, or in other words, the most common scenario is termed as an average case scenario.

## Space/Space Complexity

It tells us about how much extra space does an algorithm takes? If the algorithm requires no space then it is a good algorithm and vice versa.

## Swap Efficient

Most of the time, there's a cost associated with swapping the elements. If the swapping is expensive, then an algorithm that does minimum swapping is declared as an efficient algorithm.

## Preserves Data Integrity

This factor tells us whether the order of the same elements is maintained or not? If there are two similar elements in a collection, then the algorithm which preserves the order of the elements is a good algorithm. For example, in [5, 2, 7, 2, 1] all sorting algorithms will result in [1, 2, 2, 5, 7], but those algorithms that maintain the 2's order are stable algorithms. In order words, let's mark the similar elements [5, 2(A), 7, 2(B), 1]. Now the algorithm that gives [1, 2(B), 2(A), 5, 7] is an unstable algorithm.

## RAM Friendly

Sometimes the data is so huge that it cannot be loaded into RAM. In such a case, those algorithms which work on data stored on a hard drive are considered RAM-friendly algorithms.

There are a lot of sorting algorithms out there, but I will consider the most commonly-used/easy-to-implement algorithms, namely selection sort, insertion sort, merge sort, and quick sort. So, I have come up with a decision tree in order to solve the problem of choosing the right sorting algorithm with respect to data/situations (generally).  