Sorting algorithms

Sorting algorithms are processes to follow for sorting lists of data. They are commonly used as an introduction to algorithms for students of computer science.

There are many different strategies that can be used to sort data. These include sorting by insertion, by exchanging, by selection, by merging, and by distribution.

Sorting by Insertion

Sorting by insertion works by inserting elements back into the place where they belong in an already sorted sequence until all elements are inserted and the sequence is sorted.

The classic example of a sort by insertion is insertion sort. For the kth iteration of insertion sort, $R_{1},R_{2},...,R_{k}$ are already sorted and $R_{k+1}$ is inserted into the location in this sorted subsequence.

A more efficient sort that uses insertion is Shellsort.

Sorting by Exchanging

Sorting by exchanging works by exchanging elements that are not in the right order until the sequence is sorted.

The classic example of a sort by exchanging is bubble sort. Bubble sort works by repeatedly passing over the sequence and exchanging adjacent elements that are out of order until the whole array is in order.

A more efficient sort that uses exchanges is Quicksort.

Sorting by Selection

Sorting by selection works by selecting the element that belongs in the correct places in the sequence until all elements of the sequence are selected for their correct positions and the sequence is sorted.

The classic example of a sort by selection is selection sort. Selection sort works by finding the smallest of the unsorted portion of the sequence and placing it at the end of the sorted point of the sequence until the array is completely sorted.

A more efficient sort that uses selection is Heapsort.

Sorting by Merging

Sorting by merging works by sorting smaller subsequences then merging them together into larger sorted sequences.

The classic example of a sort by merging is merge sort. Merge sort works by dividing the seqeunce into halves repeatedly until the subsequences are trivially sorted then merging the sorted subsequences together until the whole sequence is sorted.

Sorting by Distribution

Sorting by distribution works by placing the elements into categories then putting the elements in the categories back into the sequence in sorted order. This can be faster than the other methods, but it can require a lot more memory.

The classic example of a sort by distribution is radix sort. Radix sort works by taking placing fixed-width numbers into categories based off their last digit. It then collects back the categories in order of the last digit and repeats the process for the second to last digit, and continues for each digit until the first one.