sorting.md

Sorting algorithms

Table of contents

• Comparison sorting
  • Insertion sort
  • Selection sort
  • Heap sort
  • Merge sort
    • Inversions counting
  • Order statistics
• Linear-time sorting
  • Count sort
  • Radix sort
• Other algorithms
  • Pancake sorting
  • Spreadsort

---

🔗

• Sort – Boost libraries

---

Comparison sorting

In comparison sorting one may compare two element (checking whether ai < aj). Other operations on element (e.g., using them as indices) are not allowed.

📝

• Any comparison-based algorithm of sorting an array of size n requires Ω(n log n) comparisons in the worst case. Determining the exact number of comparisons is a computationally hard problem even for small n. No simple formula for the solution is known.
• For practical applications one should always consider constant factors hidden in the big-O notation. Typically, O(n2) algorithms (e.g., insertion sort) are faster than O(n log n) ones (e.g., quick sort) for small inputs. For example, std::sort implementation in stdlibc++ resorts to the insertion sort if the input size doesn’t exceed 16 elements, and Microsoft’s implementation uses the value 32.

🔗

• Comparison sort – Wikipedia
• Minimal number of comparisons needed to sort n elements – The OEIS

🎥

• Lower bounds for sorting – MIT OCW 6.006: Introduction to algorithms (2011)

📄

• J.L.Bentley, M.D.McIlroy. Engineering a sort function – Software: Practice and experience 23, 1249 (1993)

💫 Visualizations

• Comparison sorting algorithms visualization

Insertion sort

At each iteration, insertion sort removes one element from the input data, finds the location it belongs within the sorted list, and inserts it there. It repeats until no input elements remain.

📝

• Insertion sort is commonly used to sort a small number of elements. It is employed in many std::sort implementations as a final step of recursion when a sub-range is small enough.

📖

• Ch. 9: Medians and order statistics – T.H.Cormen, C.E.Leiserson, R.L.Rivest, C.Stein. Introduction to algorithms (2009)
• Ch. 8: Elementary sorting methods, Sec.: Insertion sort – R.Sedgewick. Algorithms (1983)

Selection sort

📝

• Selection sort makes only O(n) writes in the average and the worst cases, and is useful when writes are significantly more expensive than reads, e.g. when elements have small keys and very large associated data or when elements are stored in flash memory.

🔗

• Selection sort – Wikipedia

📖

• Ch. 8: Elementary sorting methods, Sec: Selection sort – R.Sedgewick. Algorithms (1983)

Heap sort

🔧 Applications

• Implementation of std::partial_sort that rearranges a given range such that k smallest elements become the first k elements of the range, in sorted order.

Merge sort

📝

• Merge sort is useful for sorting linked lists and for external sorting of data that doesn't fit into main memory.

🔗

• Merge sort – Wikipedia

Inversions counting

Problem: count the number of inversions in a permutation P = (a1, ..., an), i.e. the number of pairs (ai, aj) with i < j and ai > aj.

📝

• The minimum number of adjacent swaps required to sort a permutation P (i.e. convert it into the identity one) is equal to the number of inversions in P.

🔗

• Counting inversions in a permutation – CS 122A: Algorithm design and analysis (2010)

🎥

• Counting the number of inversions in a permutation – CS 122A: Algorithm design and analysis (2010)

📖

• Sec. 5.3.: Counting inversions – J.Kleinberg, E.Tardos. Algorithm design (2005)

Order statistics

The k^th order statistic of an array is its k^th smallest element.

📝

• Any comparison-based algorithm of finding the smallest element in an array of size n requires at least n - 1 comparisons in the worst case.
• Any comparison-based algorithm of finding both the smallest and the largest elements in an array of size n requires at least ⌈3n / 2⌉ - 1 comparisons in the worst case.
• Any comparison-based algorithm of finding both the smallest and the second smallest element in an array of size n requires at least N + ⌈log2 N⌉ - 2 comparisons in the worst case.

🔗

• Selection and order statistics – ICS 161: Design and analysis of algorithms (1996)
• Sample proofs involving selection problems – COMP 363: Design and analysis of computer algorithms (2003)
• Lower bounds and optimality – COMP 2011/2711: Data organisation (2006)

🎥

• Order statistics, median – MIT OCW 6.046J/18.410J: Introduction to algorithms (2005)
• Lectures 6-10: Finding the smallest and second smallest elements – Alexander Stepanov: Efficient programming with components (2013)

📖

• Ch. 9: Medians and order statistics – T.H.Cormen, C.E.Leiserson, R.L.Rivest, C.Stein. Introduction to algorithms (2009)
• Sec. 6.5.2: Finding the k^th smallest element, Sec. 6.11.2: Finding the two largest elements in a set – U.Manber. Introduction to algorithms: A creative approach (1989)
• Sec. 3.6: Order statistics, Sec. 3.7: Expected time for order statistics – A.V.Aho, J.E.Hopcroft, J.D.Ullman. The design and analysis of computer algorithms (1974)

📄

• S.S.Kislitsyn. On the selection of the k^th element of an ordered set by pairwise comparison (in russian) – Sibirsky Matematichesky Zhurnal 5, 557 (1964)

---

Linear-time sorting

🎥

• Counting sort and radix sort – MIT OCW 6.006: Introduction to algorithms (2011)

Count sort

Radix sort

🔗

• Radix sort – Wikipedia
• American flag sort – Wikipedia

🎥

• M.Skarupke. Sorting in less than O(n log n): Generalizing and optimizing radix sort – C++Now (2017)

---

Other algorithms

Pancake sorting

📝

• The problem of finding the shortest sequence of flips for a given stack of pancakes is NP-hard (L.Bulteau, G.Fertin, I.Rusu, 2011)

🔗

• Pancake sorting – Wikipedia

Spreadsort

🔗

• Spreadsort – Wikipedia
• Spreadsort – Boost.Sort library