# Questions tagged [sorting]

the algorithmic problem of ordering a set of elements with respect to some ordering relation.

941 questions
Filter by
Sorted by
Tagged with
29 views

### Minimal k-way comparison sorting algorithm?

I've watched 600 TV shows, and I want to sort them in order of how much I liked them. I'm bad at assigning absolute scores, but good at comparing relative enjoyment, so it has to be a comparison sort. ...
• 21
1 vote
57 views

### Algorithm to sort array into K increasing subsets?

Let's say we got an array of size n with real numbers, and a natural number k. n must be multiple of k. We want to sort the array in a way that, when we divide this array into k subsets of equal size, ...
1 vote
25 views

### Is there a lower bound on space complexity of non-in-place sorting?

There is a well known result stating that any comparison-based sorting algorithm has a time complexity of at least O(n log n). Selection sort and merge sort are two common examples, with time ...
• 123
55 views

### Deterministic solution of "nuts and bolts" problem

How are the samples in "Matching nuts and bolts" paper in chapter two chosen deterministically to achieve $O(n^{1.5})$ complexity? I don't see how projective planes can help here.
• 41
72 views

### Is it possible to sort this type of array in O(n) time?

Pseudo-Sorted array is an array that for every 0=<k<n the k smallest cell will be in the first 2k cells. For example the smallest cell will be in indexes 0-1 The second will be in indexes 0-3 ...
49 views

### Minimize cost for list of words given a list of letters

What is a general algorithm to reorder a list of letters such that it minimizes the cost for a fixed list of words? Algorithm input To be optimized a list of unique letters: ...
• 141
1 vote
117 views

### Why is the number of array accesses not considered in analyzing the complexity of mergesort?

I'm reading Robert Sedgewick's Algorithms and in the section about The complexity of sorting, I found the following paragraph: Proposition. Mergesort is an asymptotically optimal compare-based ...
• 147
719 views

### What don't I understand in topological sort using DFS?

Wikipedia says: The algorithm loops through each node of the graph, in an arbitrary order, initiating a depth-first search that terminates when it hits any node that has already been visited since ...
• 493
30 views

### Why is it impossible to do a linear time radix sort on n integers and ranging from $0$ to $n^{3} - 1$?

I propose by doing a base-n expansion of the numbers, we have that since there are $n^{3}$ values and $n$ digits in this expansion, there are a total of $\log_{n} n^{3} = 3$ digits. Note in this base-...
• 103
12 views

### Relation between running time of Insertion sort and number of inversions

What is the relationship between the running time of insertion sort and the number of inversions in the input array? Justify your answer. Consider Insertion sort ...
1 vote
53 views

### Prove maximum score is achieved by being greedy

I have a list of tokens T, of length n. Initially I have power p and a ...
• 284
37 views

### What is the Time Complexity of Least Topological Ordering?

I knew the time complexity of Topological ordering is O(V+E) since we don't need to do sorting during the selection of node whose incoming degree is 0. But what about the least topological ordering ...
24 views

### Is this bayesian average calculation right?

I have asked it already on math.stackexchange.com and stackoverflow.com but they said it was off-topic and could not help me. They pointed me to cs.stackexchange.com so hopefully somebody here can ...
• 101
40 views

### Selection sort on the array $\{5,9,11,10,2\}$

I want to understand how the algorithm of selection sort sorts the given array, $$A[5]=\{5,9,11,10,2\}$$ Step -$1:-$ I compare A[0] with remaining elements of the array and since $A[4]<A[0]$ I swap ...
• 109
1 vote
43 views

### Bottom-up well-balanced mergesort

If you implement mergesort top-down you can always split the input of length $n$ into one of length $\lfloor n / 2\rfloor$ and one of length $\lceil n / 2 \rceil$. This ensures that all merges are ...
• 13.6k
68 views

### Correctness proof of bubble sort(bogus proof)

I am aware of bubble sort correctness proof. But what is wrong with following argument while using induction. Proof: Assume correctness of array size $1$ and $n$ (base and hypothesis). Then for ...
34 views

### given a list of 3 dimension what is the best approach to find the highest sum

We are given a file of three columns - the first is player name - the second is game item name - the third is the price of the game item when bought by the player items may repeat for the same player ...
• 101
98 views

### Is it possible to sort numbers in linear time and constant extra space?

The programming language is C++, and the elements of the input vector are of type int and able to take all valid ...
• 960
2k views

### Isn't counting sort a better sorting algorithm for linked lists rather than merge sort?

I have to analyze how every sorting algorithm's complexity would change if it had to sort a linked list and which of all of them is the most efficient. I find everywhere that merge sort is the most ...
• 73
1 vote
113 views

### How many comparative sorting algorithms are there?

I've invented an abstract structure to represent a comparison-based sorting algorithm, which I will call a comparison tree (similar to the decision tree of a comparative sorting algorithm). ...
• 51
71 views

### Sorting with element merging

I'm seeking information about a specific sorting algorithm. This algorithm performs pairwise comparisons and distinguishes between three states: a > b: In this case, standard sorting logic proceeds ...
• 121
1 vote
37 views

### Performance considerations of index maps for rearranging a vector

Imagine two vectors $V=[v_1, v_2, \ldots, v_n]$, $S=[s_1, s_2, \ldots, s_n]$ where $S$ is a rearrangement of $V$ based on some relation $\leq$. Imagine that, instead of computing $S$ using as input $V$...
• 529
93 views

### How to sort an array A using an array S with the properties below

A is an array of size n of different numbers (not necessarily integers). Indexes start from $1$ to $n$. S is an array with the property: S[i] = |\left\{A[j] \ : 1\le j<i \ \text{and} \ A[j] \le ...
• 143
32 views

### Sorting exams dividing the task between m teachers

I have to find 2 efficient ways to sort 1000 exams according to the students' last names and give the complexity. The task has to be divided between m teachers. I think one efficient way is to give ...
• 73
1 vote
108 views

### Is there a [non-comparative] sorting algorithm, sorting an array in $o(n \log n)$?

We have shown that any comparative sorting algorithm has the worst-case complexity of $\Omega(\log (n!)) = \Omega(n \log n)$, as it has to cover all the ways a permutation can be, and according to the ...
• 51
62 views

### Finding Specific Order Statistics with O(n log(n/k)) Complexity

I'm working on a problem where I need to find specific order statistics in a set of numbers. Given n numbers, I want to determine the ...
51 views

### Insertion sort - how it works

This is the pseudocode for insertion sort. My question is this: suppose I have the array [5,2,4,6,1,3]. key = 2 and i = 1. Then A[i+1] = A[i] is A[2] = A(1) = 5. So now isn't the new array [5,5,4,6,1,...
49 views

### The Festival-Clique-Sorting Problem

The following is a real world problem, for which I adjusted the explanation, such that it is easier to understand. In a very abstract form, the challenge is to find a group-sorting algorithm, that is ...
• 21
66 views

### At what case/problem, Binary Insertion Sort would be faster than Insertion Sort?

We know Insertion Sort would be faster than Merge Sort and Quick Sort for nearly sorted data. What about Binary Insertion Sort? At what case is it better than Insertion Sort? Also, is there a better ...
• 3
25 views

### maximum step of sorting network

How to calculate the maximum step of sorting network? Based on image below, it has most comparators at second index which is 9 comparators than another indices. That's mean, overall networks need 9 ...
146 views

59 views

### Efficient way of exploiting many symmetries

I have a problem domain that has several kinds of symmetries. I will try to keep this as general as possible. Given an array of strings: ["4533", "1234", ...] The two symmetries ...
24 views

### Is there any sorting algorithm that can generate all the sets of notes?

As we can visualize and listen to a sorting algorithm sorting an array, does exist an algorithm that can generate any set of notes? More precisely, does exist a sorting algorithm so that exists a ...
• 51
1 vote
15 views

### Correlation between branchless algorithm length (Assembly) and its latency

I have recently reviewed the new article by DeepMind (Google) in Nature named "Faster sorting algorithms discovered using deep reinforcement learning". They claim that branchless algorithms, ...
• 111
1 vote
146 views

### Is there an upper bound on the number of different sorting algorithms

Is there a proven upper bound on the number of possible sorting algorithms that cannot be reduced to another sorting algorithm? Sorting algorithms with "useless steps" wouldn't count because ...
4k views

### How AlphaDev improved sorting algorithms?

On the 7th of June 2023, Google DeepMind released an article about AlphaDev. AlphaDev is an evolution of AlphaZero (used to beat world champions at Go, Chess and Shogi), and it can produce assembly ...
137 views

### Comparison-based computation: percentage of current software development?

Vol. III of The Art of Computer Programming, chapter 5 (Sorting, intro) mentions: Computer manufacturers of the 1960s estimated that more than 25 percent of the running time on their computers was ...
67 views

### How does merge sort decide how to merge an array?

So, the way I understand merge sort: We split an array into two halves, then we split those halves into halves, etc. until we get arrays that can be split no further. We kind of build up a tree in the ...
• 185
1 vote
44 views

### Shell sort algorithm analysis

Given this Shell sorting algorithm implementation: ...
• 21
1 vote