# Questions tagged [sorting]

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

109 questions
Filter by
Sorted by
Tagged with
6k 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 ...
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)$ ...
2k 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 ...
2k 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? ...
706 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 ...
723 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 ...
473 views

254 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 ...
7k views

### is “spaghetti sort” really O(n) (even as a thought experiment) ?

I`m referring to the notion described here: http://en.wikipedia.org/wiki/Spaghetti_sort In the analysis section the author admits that considering it to be O(n) requires the assumption that the act ...
368 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 ...
374 views

### Computing topological sort while keeping edges “short”

Motivation: I want to compute a topological sort order in which the connected vertices are close to each other. Problem statement: Given a DAG $G(V,E)$ with $n$ vertices, compute a topological sort ...
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 ...