# Questions tagged [sorting]

Given a sequence of elements, find a permutation such that the elements are in a certain order.

126 questions
Filter by
Sorted by
Tagged with
44 views

### Possibility to Use Radix Sort for Linear Sorting of Floating Point Numbers?

Radix sort is a sorting algorithm that runs in linear time because it doesn't use algebraic comparisons. Its main limitation is that, because of this, it can only sort integers. However, a 32-bit ...
1k views

### What is the fastest static comparison sort? What is the proper term for "static"?

In a standard comparison sort, you perform a comparison and your next action is based off of the result of that comparison. What if this was not allowed, and you had to request all the results at the ...
• 299
62 views

### Is greedy minimax permutation rejecting sorting optimal?

I sketch an impractical, theoretical comparison sort for sorting array $a$ of size $n$. Initialize a list of all $n!$ permutations of size $n$. For each possible pair of indices $i, j$, count how ...
• 885
372 views

### Is sorting NP-complete?

SORTING problem. Input: A poset which corresponds to a partially sorted list of different numbers. Output: Number of pairwise comparisons needed (in the worst case) to get a completely sorted array. ...
• 14.1k
154 views

### What is best lower bound for comparison sort?

Sorting $n$ numbers requires $\lceil \log_2(n!)\rceil$ comparisons and this is asymptotically optimal, but there is an $O(n)$ error term. What is the best known lower bound for large $n$? I couldn't ...
• 14.1k
1 vote
77 views

### Can arbitrary comparator be transformed into equivalent key for radix sort?

The question is quite simple: Is it possible for any deterministic comparator of keys to be transformed into radix-sortable key mapping function? By that I mean, does for every comparator ...
1 vote
Input: A list of real numbers $[x_0, ..., x_n]$ Output: A list of integers $[d_0, ... , d_n]$ where $d_i$ is the largest $d\in\{1,\dots,i\}$ such that $$x_i\geq x_{i-1}, x_{i-2},\dots,x_{i-d}$$ In ...