# Questions tagged [sorting]

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

709 questions
Filter by
Sorted by
Tagged with
38 views

### Find the average number of steps to sort an array by randomly selecting two elements

I have sequence of an unique numbers from 1 to 10 in randomly order (for example: list = [7, 5, 3, 4, 2, 6, 10, 1, 9, 8]). I can choose two random number and if the list from left number larger then ...
34 views

### Nielsen & Chuang Exercise 3.15: Lower bound for compare-and-swap based sorts

From Nielsen & Chuang (page 138): Suppose an $n$ element list is sorted by applying some sequence of compare-and-swap operations to the list. There are $n!$ possible initial orderings of the list....
17 views

### Looking for a subjective ranking algorithm

I'm interested in learning about ranking algorithms that sort items based on preference. For example: If a person was food taster/judge and had 10 small bowls of chili that they had to rank in order ...
16 views

### In CDC 6600 6-bit encoding, why does it matter what value space character is given?

How does this affect sorting such that sort function result in: FOO BAR FOO while expecting: FOO FOO BAR Reference https://en....
26 views

### Bottom-up Mergesort vs Natural Merge Sort

I ran into natural mergesort in this Wikipedia page: https://en.wikipedia.org/wiki/Merge_sort#Natural_merge_sort However, I can't find much information regarding: The algorithm(s) to achieve natural ...
46 views

### Algorithm for sorting arrays of arrays

I have a problem where I need to sort array of arrays. For A being a array arrays (a1,a2,a3,...an) were each a = {0...d} d=fixed number of elements. *The assumption all sublists will have fixed ...
28 views

### How do we sort the chunk in the first pass of external merge sort?

Referring to the 9th page of a slide, when we use multi-pass multi-way external merge sort on a file with $N$ pages using $B$ buffer pages, in "pass 0" we'll read a chunk of $B$ pages into ...
41 views

### Why do we need MinHeap for Meeting Rooms 2 Leetcode problem

I came across this problem online which is a Leetcode premium problem. Most of the people are solving this using Minheap. To me using minHeap for this seems like repetitive way to solve a problem if ...
55 views

### Why decision tree method for lower bound on finding a minimum doesn't work

(Motivated by this question. Also I suspect that my question is a bit too broad) We know $\Omega(n \log n)$ lower bound for sorting: we can build a decision tree where each inner node is a comparison ...
32 views

### Why selection sort is a stable sort algorithm?

One of the specifications of sort algorithms is stability, which means items with the same value in different indices are not replaced after applying sort algorithm. Why selection sort is unstable and ...
48 views

### simplyfing common data values (parts of a string) in an array - by merging same attributes (data values)

I have arrays comprised of string elements like the following 2 examples. Each of the following lines is a string element of the array. example1: ...
42 views

### Error in pivot selection algorithm for merge phase [Sorting]

In the paper Comparison Based Sorting for Systems with Multiple GPUs, the authors describe the selection of a pivot element with respect to the partition on the first GPU (and its mirrored counterpart ...
18 views

### approximate line segments from array of unsorted points

The polygon above is actually a collection of a lot of black points closely packed together. I want to approximate these black points as straight line segments. The black points are not sorted in any ...
27 views

### Why do we should not to use simple count instead of cumulative count in Counting Sort?

I have this piece of code for counting sort and it is "counting" sort, because it actually counts occurrences. And it doesn't use cumulative sum. I want to ask why it is bad to not to use ...
21 views

### Sorting idea - using little buckets (Not BucketSort)

I am recently been doodling with sorting, thought about writing my own ideas, and what I am about to write here came to my mind, and I am writing it here because I do not know if such sorting idea ...
28 views

### Fast hashing algorithm for mapping/quantizing a collection of floats onto a small set of sorted floats

With my application, I have Collection X: thousands of floating-point numbers with the value range [0, 1], not sorted. Collection Y: 11 floats ranging from [0, 1], sorted. The size of X is known. Let ...
33 views

### Proof for time complexity of Insertion (k-proximate) Sort equals O(nk)

The following is the definition for Proximate Sorting given in my paper: An array of distinct integers is k-proximate if every integer of the array is at most k places away from its place in the array ...
29 views

### What factors of the integer dataset being sorted can I change, in order to compare two sorting algorithms?

I am comparing two comparison and binary data structure based sorting algorithms, the Tree Sort, and the Heap Sort. I am measuring the time taken for both algorithms to sort an increasing size of an ...
36 views

### How do you find all integers in a sorted array of size n that appear n/k times?

I try to find the solution to this problem: How do you find all integers in a sorted array of size n that appear n/k times in less than O(klogn) time? I could only find this question, where O(klogn) ...
33 views

### Why is there so little literature on partial order production?

Please excuse or improve the poor title of this question. My question is rather undirected, but I guess I am trying to find out if I might be missing a keyword for my problem. So there is plenty of ...
45 views

### Finding a Good Estimate for Amount of Time Computers Spend Sorting Lists of What Lengths?

I have an assignment to envision and calculate the possible effects the implementation of a general sorting algorithm that is O(n) time and O(1) space ( assuming general case ) would have on ...
24 views

### 2 Questions about Topological sorting in DAG

$G = (V,E)$ is a directed graph without cycles (DAG). Let $s,t \in V$ two vertices in the graph such that: exists a path from $s$ to any other vertex, and exists a path from any vertex to $t$. ...
45 views

### Minimizing the sum of differences in a pair [duplicate]

You have two arrays, a and b Both contain n elements, all positive and distinct. you have to create a pair, by taking one number from each array, such that the sum of the differences of the pairs ...
55 views

125 views

### Why does MergeSort have O(n) space complexity if it splits the array log(n) times?

I know this is a common algorithm with plenty of analysis, but when I searched for an answer the only one I found was "Merge Sorting has O(n) auxiliary space because it copies the array into L and R". ...
217 views

### MSD vs LSD Radix sort

I read the following in CRLS: I don't understand the text in yellow. Why would radix sort not work so well if we sort by their most significant digit? What extra "...
28 views

### Revert array shuffle faster than in O(n^2)

I want to reverse an array that was shuffled with the function ...
30 views

### Reverse of In-place algorithm for interleaving an array

How to do the reverse process of In-place algorithm for interleaving an array question?
45 views

### Need help analyzing the runtime analysis of this algorithm/algorithms in general

This is the algorithm I was trying to find the runtime of (doSomething) - ...