/Sorting_Algorithms

Attempts at optimal sorting algorithms.

Sorting_Algorithms

Attempts at optimal sorting algorithms.

The three target open problems in sorting are:

  1. A nlogn work logn depth Algorithm for sorting which is more practical than bitonic sort. My most noteworthy attempt is a parallelization of mergesort written in haskell, which will compared to other sorts. The algorithm is untested, and unproven.
  2. A n work logn depth Algorithm for sorting small numbers in the range [0,poly(n)] Two attempts are tinysort and smallsort. Both Algorithms are untested.
  3. A sub nlogn sorting algorithm which uses hashing and truncation. The algorithm is untested, and randomized.

Less important problems

  1. Discussing L vs NC^1 via sorting/permutation logic. Attempting a complexity theorem.
  2. Analyzing Bitonic Merge. What happens when you feed this circuit a non-bitonic sequence.