Sorting Algorithms

• Insertion sort
• Shell sort
• Gap sort

---

• Merge sort
• In-place mergesort
• Weave sort

---

• Quicksort ...

  Quicksort

  Quicksort is a divide and conquer algorithm. Quicksort first divides a large array into two smaller sub-arrays: the low elements and the high elements. Quicksort can then recursively sort the sub-arrays. The steps are:

  1. Pick an element, called a pivot, from the array.
  2. Partitioning: reorder the array so that all elements with values less than the pivot come before the pivot, while all elements with values greater than the pivot come after it.
  3. Recursively apply the above steps to the sub-array of elements with smaller values and separately to the sub-array of elements with greater values.
• Median of array (quickselect + median of medians) ...

  Quickselect

  Quickselect is a divide and conquer algorithm. It finds the k-th element in an array (for some given k) in average linear time.

  It achieves this by partitioning the array around a pivot, counting how many elements are left on each side, and discarding the side that doesn't contain the k-th element

  Median of Medians

  The median of medians algorithm is an approximate median-finding algorithm. It can be used it to discard large portions of an array when searching for the exact median, thus speeding up the search.

  In this case, we use the Quickselect algorithm, and enhance it by choosing pivots using the median of medians algorithm, which gives it worse case linear time, instead of just average.

• Deterministic Quicksort ...

  Deterministic Quicksort

  Like quicksort, but uses the "Median of Medians" algorithm to pick a pivot. This guarantees the O(n log(n)) runtime.

---

• selection sort
• heapsort
• smoothsort

What is this?

These are some sorting algorithm visualizations I made between 2017 and 2019.

Most of them are well-known algorithms, but there's also one I invented: "Gapsort". It is in a class of sorting algorithms known as "Library sorts", those being a variant of insertion sorts. Though library sorts can theoretically be implemented in O(N log N) with O(1) extra space, Gapsort is quadratic on average (though a lot faster than insertion sort).