A Textbook of Data Structures and Algorithms, Volume 3

17Internal Sorting

17.1. Introduction

Sorting in the English language refers to separating or arranging things according to different classes. However, in computer science, sorting, also referred to as ordering, deals with arranging elements of a list or a set or records of a file in ascending or descending order.

In the case of sorting a list of alphabetical, numerical or alphanumerical elements, the elements are arranged in ascending or descending order based on their alphabetical or numerical sequence number. The sequence is also referred to as a collating sequence. In the case of sorting a file of records, one or more fields of the records are chosen as the key based on which the records are arranged in ascending or descending order.

Examples of lists before and after sorting are shown below:

Unsorted lists	Sorted lists
{34, 12, 78, 65, 90, 11, 45}	{11, 12, 34, 45, 65, 78, 90}
{tea, coffee, cocoa, milk, malt, chocolate}	{chocolate, cocoa, coffee, malt, milk, tea}
{n12x, m34b, n24x, a78h, g56v, m12k, k34d}	{a78h, g56v, k34d, m12k, m34b, n12x, n24x}

Sorting has acquired immense significance in the discipline of computer science. Several data structures and algorithms display efficient performance when presented with sorted data sets.

Many different sorting algorithms have been invented, each having their own advantages and disadvantages. These algorithms may be classified into families such as sorting by exchange, sorting by insertion, sorting by distribution ...