Here, We will learn about sorting algorithms, why is sorting necessary, classification and complexity of sorting, types of sort.

**What is Sorting?**

**Sorting** refers to arranging data in a particular format.

**Sorting Algorithm** is an algorithm that arranges the elements in a certain order [either ascending or descending]. The output is reordering of the input.

Most common order are numerical or lexicographical order.

**Example** of Sorting in real life scenarios are following:

**Telephone Directory –**keeps telephone number of people sorted on their names. So, those**Dictionary –**Keeps words in alphabetical order so that searching for any word becomes easy.

**Why is Sorting Necessary?**

Sorting optimized the data searching to a high level if the data is stored in a sorted manner. It is also used to represent data in more readable formats.

It can reduce the complexity of a problem and is often used for database algorithms and searches.

**Classifications of Sorting Algorithms**

Sorting algorithms are generally categorized based on the following parameter:

**Number of Comparisons –**For comparison-based sorting algorithms, best case behaviour is*O(n log n)*and worst-case behaviour is O(n2).- Number of Swaps – categorized based on the number of swaps (also called inversions)
- Memory Usage – O(1) for in-place sorting or O(log n) memory to create auxiliary locations for sorting the data temporarily.
- Recursion – recursive (quick sort) or non-recursive (selection sort, insertion sort) and both (merge sort).
- Stability – maintain the relative order of elements with equal keys.
- Adaptability – complexity changes based on pre-sortedness (quick sort). Algorithms that take into account are known to be adaptive.

**In-place and Not-in-place Sorting**

Sorting algorithm may require some extra space for comparison and temporary storage of a few data elements.

Those algorithms do not require any extra space for sorting is called **in-place sorting. **Bubble sort is an example.

The algorithm which requires extra space for sorting is called **not-in-place sorting.** Merge sort is an example.

#### **Stable and Not Stable Sorting**

In a sorting algorithm, after sorting the elements, does not change the sequence of similar elements in which they appear, it is called **Stable Sorting.**

In a sorting algorithm, after sorting the elements, change the sequence of similar elements in which they appear, it is called **Unstable Sorting.**

**Types of Sort**

**Time and Space Complexity**

### Related:

*Want to Contribute*:-

If you like “**To The Innovation**” and want to contribute, you can mail your articles to **[email protected]**. See your articles on the main page and help other coders.