Questions tagged [sorting]

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

Filter by
Sorted by
Tagged with
39
votes
1answer
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)$ ...
38
votes
2answers
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 ...
34
votes
3answers
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)$? ...
27
votes
2answers
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 ...
25
votes
2answers
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 ...
21
votes
3answers
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? ...
21
votes
1answer
654 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 ...
19
votes
1answer
718 views

Merging lists of fragile objects

Background: Chao Xu posted the following question some time ago: "Are there any known comparison sorting algorithms that do not reduce to sorting networks, such that each element is compared $O(\log n)...
17
votes
2answers
1k views

Sorting by Euclidean distance

$S$ is a set of points on a plane. A random point $x \notin S$ is given on the same plane. The task is to sort all $y \in S$ by Euclidean distance between $x$ and $y$. A no-brain approach is to ...
16
votes
2answers
2k views

What persistent data structure for a set of partially ordered elements?

I need to store sets of elements of type a. Type a is partially ordered, so comparing $a_1$ and $a_2$ can return smaller, greater, equal or incomparable. One problem with hashtables is that two equal ...
16
votes
2answers
2k views

“Almost sorting” integers in linear time

I am interested in sorting an array of positive integer values $L = v_1, \ldots, v_n$ in linear time (in the RAM model with uniform cost measure, i.e., integers can have up to logarithmic size but ...
16
votes
1answer
253 views

Is it enough to sort for polynomially many 0-1 sequences for a sorting network?

The 0-1 principle says that if a sorting network works for all 0-1 sequences, then it works for any set of numbers. Is there an $S\subset \{0,1\}^n$ such that if a network sorts every 0-1 sequence ...
15
votes
2answers
3k views

Minimum number of transpositions to sort a list

In trying to devise my own sorting algorithm, I'm looking for the optimal benchmark to which I can compare it. For an unsorted ordering of elements A and a sorted ordering B, what is an efficient way ...
15
votes
2answers
977 views

Complexity class corresponding to sorting

Two parts of TCS are algorithms and complexity. I'll simplistically say that algorithms is the study of upper bounds, showing that you can do something (with given restricted resources), and ...
15
votes
3answers
955 views

Complexity of topological sort with constrained positions

I am given as input a DAG $G$ of $n$ vertices where each vertex $x$ is additionally labeled with some $S(x) \subseteq \{1, \ldots, n\}$. A topological sort of $G$ is a bijection $f$ from the vertices ...
14
votes
2answers
2k views

Algorithm to sort pairs of numbers

I already asked this question on stackoverflow, but maybe it is better suited for this site. The problem is: I have N pairs of unsigned integerers. I need to sort them. The ending vector of pairs ...
14
votes
2answers
1k views

Sorting using read-only stacks

Consider the following setting: we are given a stack $s$ which contains $n$ items. we can use a constant $O(1)$ number of extra stacks. we can apply the following operations on these stacks: check ...
14
votes
0answers
394 views

Is it possible to find the median with a linear size sorting network?

Is there a sorting network that makes only $O(n)$ comparisons and finds the median? The AKS sorting network sorts with $O(\log n)$ parallel steps, but here I am only interested in the number of ...
13
votes
2answers
898 views

What is a good special-case sorting algorithm?

I have a dataset which is a number of objects arranged in a 2-D grid. I know I have a strict ordering, increasing as you go left-to-right within each row, and increasing as top-to-bottom within each ...
12
votes
4answers
7k views

finding smallest k elements in array in O(k)

This is an interesting question I have found on the web. Given an array containing n numbers (with no information about them), we should pre-process the array in linear time so that we can return the ...
12
votes
3answers
326 views

Sorting “k-tonic” sequences

I hope somebody knows a ref to this, so I do not have to read the literature... Consider a sequence of numbers $x_1, \ldots, x_n$. Think about the sequence as $n-1$ intervals $[x_1, x_2], [x_2, x_3], ...
12
votes
2answers
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 ...
12
votes
2answers
472 views

Can we sort without permutations?

It is well-known that sorting permutations by transposition is in $\sf{P}$, as the minimum number of transpositions required to sort $\pi \in S_n$ is exactly $inv(\pi) = \{ (i,j) \in [n] \times [n] : ...
12
votes
1answer
855 views

Is sorting $n$ real numbers in time $O(n \sqrt{\log n})$ and linear space possible?

In the recent preprint https://arxiv.org/abs/1801.00776, it is claimed that $n$ real numbers can be sorted in time $$O(n \sqrt{\log n}), $$ and linear space. The paper seems reasonable, though I am ...
12
votes
1answer
446 views

Optimal randomized comparison sorting

So we all know the comparison-tree lower bound of $\lceil\log_2 n!\rceil$ on the worst-case number of comparisons made by a (deterministic) comparison sorting algorithm. It does not apply to ...
12
votes
0answers
248 views

Hardness of optimal sorting

For comparison-based sorting algorithms, asymptotically optimal algorithms in worst-case $\Theta(n\log n)$ comparisons are well known. From a purely theoretical perspective, however, exactly optimal ...
11
votes
2answers
407 views

Linear time algorithm for finding shifted max

Assume that we are given an array $A[1..n]$ containing nonnegative integers (not necessarily distinct). Let $B$ be $A$ sorted in the nonincreasing order. We want to compute $$m = \max_{i\in [n]} B[i]...
11
votes
2answers
266 views

Determining what can be achieved by a permutation of elements of a noncommutative group

Fix a finite group $G$. I am interested in the following decision problem: the input is some elements of $G$ with a partial order on them, and the question is whether there is a permutation of the ...
11
votes
0answers
3k views

Efficient recognition of sequences sortable by transpositions?

While reading the post, Probability of generating a desired permutation by random swaps, by Aaronson, I got interested in restricted sorting problem: If we restrict sorting algorithms to use ...
11
votes
1answer
758 views

Enumerating topological sorts of a vertex-labeled DAG

Let $G = (V, E)$ be a directed acyclic graph, and let $\lambda$ be a labeling function mapping each vertex $v \in V$ to a label $\lambda(v)$ in some finite alphabet $L$. Writing $n := |V|$, a ...
10
votes
1answer
369 views

Sorting with an average of $\mathrm{lg}(n!)+o(n)$ comparisons

Is there a comparison-based sorting algorithm that uses an average of $\mathrm{lg}(n!)+o(n)$ comparisons? Existence of a worst-case $\mathrm{lg}(n!)+o(n)$ comparison algorithm is an open problem, but ...
9
votes
1answer
681 views

Can we get a sorted list from a sorted matrix in $O(n^2)$

I'm confused. I want to prove that that the problem of sorting a $n$ by $n$ matrix i.e. the rows and columns are in ascending order is $\Omega(n^2\log n)$. I proceed by assuming that it can be done ...
9
votes
1answer
406 views

Complexity of blind sort?

We all know that the minimal complexity of a comparison-based sorting algorithm is $\Omega(n \log n)$ comparisons. I'm trying to do a blind sort, i.e. given a number $n$ output a circuit (with boolean,...
9
votes
1answer
285 views

Heapsort:Heaps =~ Quicksort:BSTs =~ Mergesort:___?

Please excuse the terseness of the title, I may have sacrificed clarity on the altar of conciseness. One can see that inserting elements of an array into a binary search tree and reading them back ...
8
votes
1answer
1k views

what advantage does heapsort has over smoothsort?

Wikipedia states that the advantages of smoothsort over heapsort is that at times it comes closer to O(n) time. Now I was wondering what advantage does heapsort has over smoothsort? Or to rephrase ...
8
votes
1answer
225 views

Original reference for Huffman shaped Merge Sort?

What is the first publication of the concept of optimizing merge sort by identifying sequences of consecutive positions in increasing orders (aka runs) in linear time; then repeatedly merging the ...
8
votes
1answer
388 views

Complexity of sorting

It is not difficult to show that sorting an array of numbers is hard for $\mathsf{TC^0}$. If the input is an array of 1s and 0s then it is essentially the function $Count$ (given $n$ bits, output the ...
8
votes
1answer
911 views

Efficiently finding the minimum number of transpositions needed to sort a list

I'd like an efficient method for calculating the minimum number of transpositions needed to sort a list. I don't need to know what the transpositions actually are. For example, the list [1, 1, 2, 0] ...
8
votes
2answers
285 views

Asymptotic complexity of sorting using k-comparisons

Sorting using 2-elements comparisons has an asymptotic worst-case complexity of $n \log_2(n)$ (reached by mergesort, heapsort, binary insertion, ford-johnson at least), which is optimal. If we sort ...
8
votes
1answer
227 views

Hierarchical sorting strategies for pattern-avoiding permutations?

For a class $\mathcal{C}$ of permutations, we cannot expect to sort the permutations of $\mathcal{C}$ with less than $O(\log |\mathcal{C}_n|)$ comparisons, where by convention $\mathcal{C}_n := \...
8
votes
0answers
251 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 ...
7
votes
1answer
366 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 ...
7
votes
1answer
329 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 ...
7
votes
1answer
205 views

Sorting using ring operations

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 ...
7
votes
2answers
237 views

Are there [good/optimal] parallel comparison sorts?

Comparing each pair of elements and sorting according to [[number less than] minus [number greater than]] is a parallel comparison sorting algorithm with a depth of $1$ comparison and $O\left(n^2\...
6
votes
5answers
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 ...
6
votes
1answer
380 views

Would an optimal sorting network ever have to swap two numbers the “wrong” way

Intuitively it seems like an optimal (either minimum depth or minimum gates) sorting network should never have to compare-swap two numbers the "wrong" way (such that the larger one goes into the ...
6
votes
2answers
170 views

Quick-select contiguous subarray

Motivated by the question from this blog post, the following data structure question seems interesting and fun to me. Preprocess: A list of numbers $A = a_1,...,a_n$ Query(s,t,k): Return the $k$-th ...
6
votes
1answer
169 views

Is sorting pairwise distances as hard as sorting arbitrary points?

If we have $n$ points in $\mathbb{R^d}$, what is the complexity of sorting the $O(n^2)$ pairwise distances? Clearly the complexity is $\Omega(n^2)$ but is there a reduction to show it is as hard as ...
6
votes
0answers
257 views

Most efficient inplace merge algorithms (stable and unstable)

I am currently researching the best algorithms available to achieve an inplace merge operation: consider two consecutive sorted arrays of size n and ...