Sorting Algorithm

by codecrucks · Published 09/09/2021 · Updated 08/06/2022

In computer science, sorting algorithm is used to arrange data in specific order. This data could be in any form, may be numeric, character, string or a large record.

Sorting is a process of arranging elements in a certain order. Numeric data may be sorted in ascending or descending order. Alphabets or strings may be sorted in lexicographical order.

There are several items in our daily lives that we must search for, such as a certain record in a database, roll numbers in a merit list, a specific telephone number in a telephone directory, a specific page in a book, and so on. All of this would have been a disaster if the data had remained unorganized and unsorted, but thankfully, the notion of sorting evolved, making it simpler for everyone to place data in an order, making it easier to search.

Why Are Sorting Algorithms Important?

Sorting is a topic that has been extensively researched and investigated in the field of computer science. Sorting is a fundamental need in many applications.

Sorting data makes it easier to search through a given data sample, efficiently and quickly.

A quick Google search indicates that approximately 40 distinct sorting algorithms are now in use in the computing industry.

For sorting, there is a large class of algorithms available. All have limitations and are limited to a certain application domain. There is no algorithm that can fulfill all objectives. However, the most often used measure for selecting the optimal algorithm is running time.

Categories of Sorting

The techniques of sorting can be divided into two categories. These are:

Internal sorting
External sorting

If numbers of elements are small enough to sort in main memory, sorting is called internal sorting.

If numbers of elements are large such that some of them reside on external storage during the sorting procedure, it is called external sorting.

Properties of Sorting Algorithm

Following are the properties of sorting algorithms:

In place : Only require constant additional space to sort the algorithm. Sometimes O(log n) space is allowed.
Stable: Does not alter the relative position of same elements after sorting
Online: Sort the data as it arrives
Adaptive: Performance of algorithm varies with the input sequence
Incremental: Build sorted sequence one number at a time

Complexity of Sorting Algorithm

The complexity of a sorting algorithm measures the running time of a function with ‘n’ items to sort. The decision of which sorting technique is appropriate for a problem is determined by several dependency configurations for various problems. The following are the most important considerations:

The amount of time taken by a programmer in developing a certain sorting program.
The amount of machine time required to run the program
The amount of memory required to run the program

Efficiency of Sorting Algorithm

The complexity of algorithm is determined based on how many comparison it does to sort given data. Sorting algorithms are sensitive to arrangement of input data.

Algorithms are analyzed based on following cases:

Best case
Worst case
Average case

Types of Sorting Algorithm

Comparison Based Sorting:

In comparison based sorting methods, data are sorted by comparing two data elements. The comparator function is defined to compare and sort the data. Example: Selection sort, Bubble sort, Insertion sort

Counting Based Sorting:

These sorting algorithms make no comparisons between elements and instead rely on calculated assumptions during execution. Example: Radix sort, Bucket Sort, Counting sort

In-place vs Not in-place Sorting:

In data structures, in-place sorting algorithms change the ordering of array items within the original array. Not-in-Place sorting methods, on the other hand, sort the original array using an auxiliary data structure.

Examples of in-place algorithms are Quick sort, Insertion sort, Selection sort

Examples of not in-place algorithm is Merge sort

Some Popular Sorting Algorithms

Following are the few popular sorting algorithms used in computer science:

Additional Reading: Comparison of adaptive algorithms