Sorting - AlgoViz

Home
Sorting

Sorting algorithms

Overview

A sorting algorithm is an algorithm that puts elements of a list in a certain order (thus sorting the list). The most frequently used orders are numerical order for lists of numbers and lexicographical order for lists of strings.

To put it more formally, the output generally has to fulfill two conditions:

The output is in nondecreasing order
The output is a permutation of the input

Or, to put it simply, when running a sorting algorithm we expect an output that contains all the elements originally present in the input arranged in such a way that the smallest element (according to the operation used to sort the list) is in the leftmost place, with every element following being either bigger or equal to its predecessor.

Sorting algorithms can generally be classified into three distinct categories:

Comparison sorts
Non-comparison sorts
Others

On this page, you can find many implementations for every category. If you need a visualization for a certain algorithm, just use the search function to find it quickly.

Search

Comparison Sorts

A comparison sort is a type of sorting algorithm that only reads the list elements through a single abstract comparison operation that determines which of two elements should occur first in the final sorted list.

Bubble Sort

Bubblesort is a simple sorting algorithm that repeatedly steps through the list, compares adjacent elements, and swaps them if they are in the wrong order.

Best-case: O(n)
Average-case: O(n²)
Worst-case: O(n²)

Cocktail Shaker Sort

Cocktail Shaker Sort is a variation of bubble sort that sorts in both directions on each pass through the list.

Best-case: O(n)
Average-case: O(n²)
Worst-case: O(n²)

Comb Sort

Combsort is an extension of bubble sort. It compares elements divided by a gap which shrinks after each pass through the list.

Best-case: O(n log n)
Average-case: O(n²)
Worst-case: O(n²)

Gnome Sort

The gnome sort is a sorting algorithm that is similar to insertion sort but sorts by a series of swaps, similar to bubble sort.

Best-case: O(n)
Average-case: O(n²)
Worst-case: O(n²)

Insertion Sort

Insertion sort is a simple sorting algorithm that builds the final sorted list one item at a time by inserting each element at its correct position.

Best-case: O(n)
Average-case: O(n²)
Worst-case: O(n²)

Merge Sort

Mergesort is a divide-and-conquer algorithm that works by dividing the unsorted list into two approximately equal sublists, sorting them, and then merging them back together.

Best-case: O(n log n)
Average-case: O(n log n)
Worst-case: O(n log n)

Quick Sort

Quicksort is a divide-and-conquer algorithm. It selects a pivot element, partitions the array into two sub-arrays, and then sorts them recursively.

Best-case: O(n log n)
Average-case: O(n log n)
Worst-case: O(n²)

Selection Sort

Selection sort repeatedly selects the smallest remaining element and swaps it with the first unsorted element, building a sorted list one element at a time.

Best-case: O(n²)
Average-case: O(n²)
Worst-case: O(n²)

Non-Comparison Sorts

Non-Comparison Sorts are sorting algorithms that sort a given input without comparing the elements, instead making certain assumptions about the data. Examples include Counting Sort, which sorts using key-value, and Bucket Sort, which examines bits of keys.

Counting Sort

Counting sort is an algorithm for sorting a collection of objects according to keys that are small integers. It operates by counting the number of objects that have each distinct key value, and using arithmetic on those counts to determine the positions of each key value in the output sequence.

Time complexity: O(n+k)
with n being the number of elements and k being the number of keys.

Radix Sort

Radix sort avoids comparison by creating and distributing elements into buckets according to their radix. For elements with more than one significant digit, this bucketing process is repeated for each digit while preserving the ordering of the prior step, until all digits have been considered.

Time complexity: O(nw)
with n being the number of elements and w being the key length.

Others

Algorithms in this category are impractical for real-life use in traditional software contexts due to extremely poor performance or specialized hardware requirements. These sorts are usually described for educational purposes to demonstrate how the runtime of algorithms is estimated.

Bogo Sort

Bogosort is a highly inefficient sorting algorithm based on the generate and test paradigm. The function successively generates permutations of its input until it finds one that is sorted. An analogy for the working of the algorithm is to sort a deck of cards by throwing the deck into the air, picking the cards up at random, and repeating the process until the deck is sorted.

Best-case: O(n)
Average-case: O((n+1)!)
Worst-case: unbounded