Most Popular Sorting Algorithms

This section describes some most popular sorting algorithms - Selection Sort, Insertion Sort, Bubble Sort, Quicksort, Merge Sort, Heap Sort and Shell Sort.

There are many sorting algorithms have been developed over the years. I will only try to cover the following popular ones in this book:

Insertion Sort - A simple and slow sorting algorithm that repeatedly takes the next element from the un-sorted section and inserts it into the sorted section at the correct position.

Selection Sort - A simple and slow sorting algorithm that repeatedly selects the lowest or highest element from the un-sorted section and moves it to the end of the sorted section.

Bubble Sort - A simple and slow sorting algorithm that repeatedly steps through the collection, compares each pair of adjacent elements and swaps them if they are in the wrong order.

Quicksort - A complex and fast sorting algorithm that repeatedly divides an un-sorted section into a lower order sub-section and a higher order sub-section by comparing to a pivot element.

Merge Sort - A complex and fast sorting algorithm that repeatedly divides an un-sorted section into two equal sub-sections, sorts them separately and merges them correctly.

Heap Sort - A complex and fast sorting algorithm that organizes original collection into a heap which is a binary tree with every node higher that its children in order, then repeatedly takes the root node to the end of the sorted section and rebuilds the heap with remaining notes.

Shell Sort - A complex and fast sorting algorithm that repeatedly divides the entire collection into sub-collections by taking every h-th element for a fixed gap h and performs an insertion sort each sub-collection.