# Questions tagged [sorting]

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

22 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
390 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 ...
247 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 ...
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 ...
756 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 ...
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 ...
255 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 ...
1k views

### Minimum Number of Adjacent Swaps to Sort Numbers on a 2D Grid

Assume that we have $N$ numbers (labeled from $1$ to $N$) that are placed on a 1D (linear) array. For example, for $N=5$: If we want to sort these numbers with the minimum number of adjacent swaps (i....
159 views

### What is the best upper bound known for the complexity of computing an optimal prefix free code in the RAM model?

In the algebraic decision tree, the result is clear: Elmasry and Belal (Verification Of Minimum Redundancy Prefix Codes)'s lower bound shows that the worst case complexity of computing an optimal ...
93 views

### Is there any efficient Network stable sort (not bubble sort)?

Ok, I realize Bitonic sort is not stable and any attempt to make it stable is inefficient, or is there some efficient way? But is there some other network sort which is indeed stable beside bubble ...
119 views

16 views

### Why is it more efficient to merge larger runs higher in the tree than perform a balanced tree of merges in an unbalanced ping-pong merge?

While studying the research paper published by Microsoft in 2014, I stumbled upon Unbalanced Ping-Pong Merge. In section 3.2 of the paper, it discusses about merging two sorted runs at a time. It ...