In-Depth Sorting Algorithms

Şerifhan Işıklı

Published in

lTunes Tribe

6 min readJul 22, 2022

Stability;

A sorting algorithm is stable if it preserves the relative order of equal elements after sorting.

In place;

A sorting algorithm is in-place if it sorts using only O(1) auxiliary memory (not counting the array that needs to be sorted).

Best case complexity;

A sorting algorithm has a best case time complexity of O(T(n)) if its running time is at least T(n) for all possible inputs.

Average case complexity;

A sorting algorithm has an average case time complexity of O(T(n)) if its running time, averaged over all possible inputs, is T(n).

Worst case complexity;

A sorting algorithm has a worst case time complexity of O(T(n)) if its running time is at most T(n).

Stability in Sorting

Stability in sorting means whether a sort algorithm maintains the relative order of the equals keys of the original input in the result output. So a sorting algorithm is said to be stable if two objects with equal keys appear in the same order in sorted output as they appear in the input unsorted array.

Consider a list of pairs:

(1, 2) (9, 7) (3, 4) (8, 6) (9, 3)

Now we will sort the list using the first element of each pair.

A stable sorting of this list will output the below list:

(1, 2) (3, 4) (8, 6) (9, 7) (9, 3)

Because (9, 3) appears after (9, 7) in the original list as well.

An unstable sorting will output the below list:

(1, 2) (3, 4) (8, 6) (9, 3) (9, 7)

Unstable sort may generate the same output as the stable sort but not always.

Well-known stable sorts: Merge sort, Insertion sort ,Radix sort, Tim sort, Bubble Sort
Well-known unstable sorts: Heap sort Quick sort

Bubble Sort

The BubbleSort compares each successive pair of elements in an unordered list and inverts the elements if they are not in order.

The following example illustrates the bubble sort on the list {6,5,3,1,8,7,2,4} (pairs that were compared in each step are encapsulated in ‘**’):

After one iteration through the list, we have {5,3,1,6,7,2,4,8}. Note that the greatest unsorted value in the array (8 in this case) will always reach its final position. Thus, to be sure the list is sorted we must iterate n-1 times for lists of length n.

Implementation in JavaScript

Merge Sort

Merge Sort is a divide-and-conquer algorithm. It divides the input list of length n in half successively until there are n lists of size 1. Then, pairs of lists are merged together with the smaller first element among the pair of lists being added in each step. Through successive merging and through comparison of first elements, the sorted list is built.

Time Complexity: T(n) = 2T(n/2) + Θ(n)

The above recurrence can be solved either using Recurrence Tree method or Master method. It falls in case II of Master Method and solution of the recurrence is Θ(nLogn). Time complexity of Merge Sort is Θ(nLogn) in all 3 cases (worst, average and best) as merge sort always divides the array in two halves and take linear time to merge two halves.

Auxiliary Space: O(n)

Algorithmic Paradigm: Divide and Conquer

Sorting In Place: Not in a typical implementation

Stable: Yes

Merge Sort Implementation in Java

Quicksort

Quicksort is a sorting algorithm that picks an element (“the pivot”) and reorders the array forming two partitions such that all elements less than the pivot come before it and all elements greater come after. The algorithm is then applied recursively to the partitions until the list is sorted.

Example :

Counting Sort

Counting sort is an integer sorting algorithm for a collection of objects that sorts according to the keys of the objects.

Steps

1. Construct a working array C that has size equal to the range of the input array A.

2. Iterate through A, assigning C[x] based on the number of times x appeared in A.

3. Transform C into an array where C[x] refers to the number of values ≤ x by iterating through the array, assigning to each C[x] the sum of its prior value and all values in C that come before it.

4. Iterate backwards through A, placing each value in to a new sorted array B at the index recorded in C. This is done for a given A[x] by assigning B[C[A[x]]] to A[x], and decrementing C[A[x]] in case there were duplicate values in the original unsorted array.

Example of Counting Sort

Odd-Even Sort

An Odd-Even Sort or brick sort is a simple sorting algorithm, which is developed for use on parallel processors with local interconnection. It works by comparing all odd/even indexed pairs of adjacent elements in the list and, if a pair is in the wrong order the elements are switched. The next step repeats this for even/odd indexed pairs. Then it alternates between odd/even and even/odd steps until the list is sorted.

Selection Sort

Selection sort is a sorting algorithm, specifically an in-place comparison sort. It has O(n2) time complexity, making it inefficient on large lists, and generally performs worse than the similar insertion sort. Selection sort is noted for its simplicity, and it has performance advantages over more complicated algorithms in certain situations, particularly where auxiliary memory is limited.

The algorithm divides the input list into two parts: the sublist of items already sorted, which is built up from left to right at the front (left) of the list, and the sublist of items remaining to be sorted that occupy the rest of the list.

Initially, the sorted sublist is empty and the unsorted sublist is the entire input list. The algorithm proceeds by finding the smallest (or largest, depending on sorting order) element in the unsorted sublist, exchanging (swapping) it with the leftmost unsorted element (putting it in sorted order), and moving the sublist boundaries one element to the right.