# Questions tagged [sorting]

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

780 questions
Filter by
Sorted by
Tagged with
148 views

883 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". ...
773 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 "...
32 views

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

I want to reverse an array that was shuffled with the function ...
102 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) - ...
55 views

### How to sort objects based only on “less than” relationships?

Say I have n objects, each with an unknown value, and a n by n matrix Z. Such that Z(i,j)=1 if the value of object i is less than the value of object j, and Z(i,j)=0 otherwise. How can I sort these n ...
463 views

### Find and sort 2d array elements like radar

I don't know relevant keywords about this algorithm. I can show you visually Any ideas are appreciated
63 views

### Numerical Accuracy & Sorting Algorithms?

Sedgewick and Wayne talk about how sorting algorithms and, specifically, priority queues are used in devising ways to improve accuracy in floating-point calculations: https://algs4.cs.princeton.edu/...
217 views

### Sorting array of strings (with repetitions) according to a given ordering

We get two arrays: ordering = ["one", "two", "three"] and ...
27 views

### practise resources for basic sorting

I have to prepare for a midterm and I am looking for a resource where I can practise the three basic sorting algorithms insertion sort, bubble sort and selection sort a little. Last year they had to ...
83 views

### “Searching and sorting” algorithm to find the natural logarithim of a number?

Yeah, this is for a homework assignment, but I hope that you'll humor me anyway. I am asked to design an algorithm that finds the natural logarithm of a number. This would be straightforward, but I'm ...
20 views

### How do i tell if a network is not sorting network? [duplicate]

For most sorting network diagrams how do you work out that it is not a sorting network? What is the method to work it out ?
277 views

### Linear algorithm to measure how sorted an array is

I've just attended an algorithm course, in which I've seen many sorting algorithms performing better or worse depending on how much the elements of an array are sorted already. For example, for what I'...
195 views

### Name for sorting algorithm “while not sorted, swap the FIRST unordered pair”

A typical bubble sort steps through all pair indices until it reaches the end of the list, then starts a new pass. For a toy problem, we have a variant that just performs the first available swap in ...
6k views

### Time complexity of insertion in linked list

Apologies if this question feels like a solution verification, but this question was asked in my graduate admission test and there's a lot riding on this: What is the worst case time complexity of ...