Sorting refers to arranging a list of elements into a particular order , which may be ascending or descending.

Several programming solutions rely on sorting algorithms. They are widely used in

• Making searching algorithms efficient.
• Making raw data simpler.
• Processing data in defined order.

In-Place Sorting Vs Out-of-Place Sorting.

In-Place Sorting.

The In-Place sorting algorithm sorts the input without any additional memory. The input is usually overwritten by the output. A small amount of extra memory may be required for an in-place algorithm, but this memory requirement should not depend on the input size. So the space complexity of the algorithm is O(1). Insertion sort , Quick sort , Selection sort , bubble sort , heap sort are some of the In-Place sorting algorithms.

Out-Of-Place Sorting

Out-of-Place sorting takes additional space for the sorting. The size of the additional space depends on the size of the input. Merge sort is an Out-Of-Place sorting algorithm.

Stable Vs Not Stable Sorting

Stable Sorting

Stable sorting algorithm maintains the relative position of the similar elements after sorting. For example: In the below image the relative order of 5 is preserved after sorting.

Merge sort . Insertion sort , Bubble sort are some of the stable sorting algorithms.

Not Stable Sorting

The relative position of the same elements are not necessarily preserved in non stable sorting. Selection sort , Quick sort , Heap sort are some of the non stable sorting algorithms.

Internal Vs External Sorting

Internal Sorting

If the data sorting process takes place entirely within the main memory(RAM) of the computer it's called Internal sorting. Its possible only when the size of the list is small enough to be stored in the RAM. Bubble sort , Insertion sort , Quick sort , Selection sort are some of the common internal sorting algorithms.

External Sorting

External sorting is used when we need to sort large datasets , Which may not be stored as a whole in Main memory. External merge sort is an example of an external sorting algorithm.

Adaptive vs Non Adaptive sorting

Adaptive Sorting

If the sorting algorithm takes advantage of existing presortedness in the input list then its called adaptive sorting algorithm. Quick sort , Insertion sort , bubble sort are some of the adaptive sorting algorithms.

Non Adaptive sorting

In Non Adaptive sorting algorithms the order of the input doesn't matters. The time complexity will always remain the same for any order of the input.

Selection sort , Merge sort ,Heap sort are some examples of non Adaptive sorting algorithms.