Introduction

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

Adaptability

In adaptive algorithms, the running time changes based on whether or not the input array is sorted. If the array is pre-sorted, the running time is better compared to when it is not.

This book

In this book, we’ll review several sorting algorithms, their algorithms, performance (time and space complexity), and code examples in popular languages. We’ll start with two simple sorting algorithm, insertion sort, bubble sort selection sort. These are easy to understand, but inefficient on large data sets. We’ll also study efficient algorithms in this book like:

• Merge sort
• Heap sort
• Quick sort
• Shell sort

This is a CodeAhoy free book so please feel free to distribute it. You are encouraged to leave comments to add your thoughts or to improve the chapters in any way. Thanks.