# Introduction

#### In this chapter

In computer science, a sorting algorithm is one that rearranges the contents of a list in a specific order. The most common sort orders are numerical and lexicographical, and they can be ascending or descending. For example, given an unsorted array [3, 1, 2], a sorting algorithm would sort the elements as [1,2,3] or [3,2,1] depending on whether it’s been asked to sort in ascending or descending.

## Why is sorting important?

Besides producing output in human readable forms, sorting is vital for improving the performance of other algorithms that require input data to be in sorted lists, such as search and merging algorithms. Sorting reduces the complexity of these problems. For example, in order for us to use the binary search algorithm to find an element in the array, the array must be sorted first or binary search would fail.

## Classification of sorting algorithms

Sorting algorithms can be categorized by:

#### Best, worst and average case behavior

A good sorting algorithm would require O(N log N) operations whereas a poor algorithm takes $$O\left(N^{2}\right)$$.

#### Memory usage

Some sorting algorithms are in-place and others are not. In place algorithms don’t require extra memory and sort the array “in place” (usually by swapping elements). In-place sorting algorithms require O(1) memory. Broadly speaking, sorting algorithms requiring O(log N) space are also considered in-place for example Quick sort that we’ll review later.

#### Stability

A sorting algorithm is said to be stable if two objects with equal keys

Stable sorting algorithms maintain the order of elements with equal keys. They appear in the same order in sorted output as they appear in the input array to be sorted. A “stable” sorting algorithm keeps the items with the same sorting key in order.

Suppose we have a list of 5-letter words:

peach
straw
apple
spork


If we sort the list by just the first letter of each word then a stable-sort would produce:

apple
peach
straw
spork


In an unstable sort algorithm, straw or spork may be interchanged, but in a stable one, they stay in the same relative positions (that is, since straw appears before spork in the input, it also appears before spork in the output). source