# 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.