← Back to mit.katmh.com

Linear Sorting

· Read 03/03/2021

  • Key point: Lower bound on comparison-based sorting is Ω(nlogn)\Omega(n \log n)
  • How to get around it?

    • Take advantage of constant time to access in arrays (leave the comparison models)
    • Restrict the allowed inputs

Direct Access Array Sort

  • Items must have unique keys from a bounded positive range {0,...,u1}\{0, ..., u-1\} (so nun \leq u)
  • Construct a direct access array of size uu, insert each item xx into x.keyx.key, then read array left to right
  • Inserting takes Θ(n)\Theta(n) time, initializing and scanning take Θ(u)\Theta(u) time, so overall Θ(n+u)\Theta(n+u). If u=O(n)u = O(n), then this algorithm is linear
  • Drawbacks: Cannot handle duplicate keys and large key ranges

Counting Sort

  • Link a chain to each direct acess array index; when multiple items have the same key, store them both in the chain associated with their key
  • For the algorithm to be stable (items with duplicate keys appear in same order in input and output), choose chains that support a sequence queue interface, inserting to end of queue and returning items back in order of insertion
  • O(u)O(u) to initialize chains, O(n)O(n) to insert all the elements, O(u)O(u) to scan back through; overall O(n+u)O(n+u), which is linear when u=O(n)u = O(n)
  • Cumulative sums: keep track of how many of each key map to each index, then move each item only once (instead of moving item into chain and then back into place)

Tuple Sort

  • To handle large key ranges, we'll break up integer keys into parts, then sort each part. To do hat, we'll need a strategy to sort multiple parts, i.e. tuples
  • Use a stable sorting algorithm as a subroutine, work from least to most important key

Radix Sort

  • Break each integer into its multiples of powers of nn, representing each item key as its sequence of digits when represented in base nn
  • If the integers are non-negative and the largest integer in the set is uu, then this base nn number will have lognu\lceil \log_n u \rceil digits
  • Run tuple sort from least to most significant digit
  • If the largest integer in the set uncu \leq n^c, then radix sort runs in O(nc)O(nc) time