# 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
1answer
148 views

2answers
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". ...
1answer
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 "...
2answers
32 views

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

I want to reverse an array that was shuffled with the function ...
2answers
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) - ...
1answer
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 ...
2answers
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
1answer
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/...
3answers
217 views

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

We get two arrays: ordering = ["one", "two", "three"] and ...
1answer
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 ...
1answer
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 ...
0answers
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 ?
2answers
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'...
1answer
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 ...
4answers
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 ...
1answer
856 views

### Sorting strings using Counting Sort in O(n), where n is the total number of characters in all the strings

Suppose, you are given an array of strings of different lengths, but the total number of characters over all the strings is n. Describe an algorithm using Counting Sort to sort the strings in ...
1answer
28 views