14. Sorting

Sorting puts elements of an array or linked list in order. The order can be ascending or descending. We can sort numbers in ascending or descending order, or characters or strings in lexicographical order. This helps in producing a list of items that we can easily search through, analyze, visualize and understand. Sorting is used in many applications, including database systems, word processors, and web browsers.

There are several sorting algorithms, but will only focus on:

1. Insertion Sort

2. Selection Sort

3. Bubble Sort

4. Quicksort

Disclaimer: We discuss these sorting algorithms to sort integers in an array in ascending order. The same algorithms can be used to sort integers in descending order or to sort characters or strings in lexicographical order or to sort nodes in a linked list. However, we will not discuss these variations in this chapter.