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 names can be searched easily.
- 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
Want to Contribute:-
If you like “To The Innovation” and want to contribute, you can mail your articles to