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)$ ...
15
votes
3answers
913 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 ...
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 ...
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 ...
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 ...
19
votes
1answer
710 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)...
15
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 ...
14
votes
2answers
856 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 ...
12
votes
1answer
418 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 ...
10
votes
1answer
326 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 ...
13
votes
2answers
3k views

Lexicographically minimal topological sort of a labeled DAG

Consider the problem where we are given as input a directed acyclic graph $G = (V, E)$, a labeling function $\lambda$ from $V$ to some set $L$ with a total order $<_L$ (e.g., the integers), and ...
13
votes
2answers
847 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 ...
2
votes
1answer
317 views

Finding max of two elements in linear time with restriction

I have a matrix in the following form: ...
16
votes
1answer
243 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 ...
5
votes
1answer
482 views

Heap with $O(1)$ delete-key

Fibonacci heaps have $O(1)$ insertion and $O(\log n)$ delete-min and delete-key (under amortized complexity). Is there a heap data structure with $O(1)$ insertion and delete-key and $O(\log n)$ ...
3
votes
1answer
99 views

how to achieve a topological sort of an given sequence with minimum swaps

For example, given the constraints {$a<b,c<d$} and a sequence $[b,a,c,d]$. we just need swap $a$ with $b$ to get an topological sort, I want to ask how to find the sort solutions with minimum ...
2
votes
1answer
439 views

Stable comparison sort with $O(1)$ auxiliary memory and $O(n \log n)$ average running time

Does there exist a stable comparison sort using $O(1)$ auxiliary memory and achieving $O(n \log n)$ average run time? Context: There are comparison sorts with any two of those three desirable ...