# Questions tagged [sorting]

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

105 questions
Filter by
Sorted by
Tagged with
2k views

### Sorting algorithm, such that each element is compared $O(\log n)$ times, and doesn't depend on a sorting network

Are there any known comparison sorting algorithms that do not reduce to sorting networks, such that each element is compared $O(\log n)$ times? As far as I know, the only way to sort with $O(\log n)$ ...
5k views

### Han's $O(n \log\log n)$ time, linear space, integer sorting algorithm

Is anyone familiar with Yijie Han's $O(n \log\log n)$, linear space, integer sorting algorithm? This result appears in a fairly short paper (Deterministic sorting in $O(n \log\log n)$ time and linear ...
1k views

### Comparison-based data structure for finding items

Is there a data structure that takes an unordered array of $n$ items, performs preprocessing in $O(n)$ and answers queries: is there some element $x$ on the list, each query in worst time $O(\log n)$? ...
1k views

### Is it possible to find if a sequence exists in polynomial time in the following problem?

I've been thinking about the following problem for a time, and I haven't found a polynomial solution for it. Only brute-fource. I've been trying to reduce an NP-Complete problem into it too with no ...
3k views

### Exact number of comparisons to compute the median

Volume III of Knuth's The Art of Computer Programming (chapter 5, verse 3.2) includes the following table listing the exact minimum number of comparisons required to select the $t$th smallest element ...
572 views

### Approximate 1d TSP with linear comparisons?

The one-dimensional traveling salesperson path problem is, obviously, the same thing as sorting, and so can be solved exactly by comparisons in $O(n\log n)$ time, but it is formulated in such a way ...
1k views

### Sorting using a black box

Assume that we want to sort a list $S$ of $n$ real numbers. Assume that we are given a black box that can sort $\sqrt n$ real numbers instantly. How much advantage can we gain using this black box? ...
710 views

2k views

### Reversing a list using two queues

This question is inspired by an existing question about whether a stack can be simulated using two queues in amortized $O(1)$ time per stack operation. The answer seems to be unknown. Here is a more ...
454 views

249 views

### For median is it optimal to compare in pairs first?

Median can be done in linear time and is now down to (I think) $2.97n$. The lower bounds is (I think) $(2+\epsilon)n$ where $\epsilon$ is very small. The following theorem, if true, may help improve ...
361 views

### Optimal comparison-based stable sorting in constant space

For a comparison based sorting algorithm, it is desirable to: Be stable Run in $O(n\ \log n)$ Operate in $O(1)$ space I can find algorithms that satisfy any two of these but I can't find any that ...
Sorting is in $\mathsf{NP}$. Given a sorted list, it is trivial to check sortedness in linear time. Is there any evidence sorting of elements from an ordered gcd domain(eg: $\Bbb Z$) cannot be done ...