# Sorting

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.