The tag has no usage guidance.

37 questions
Filter by
Sorted by
Tagged with
35 views

### Calculating the Time complexity using Radix sort

Im trying to determine what is the time complexity of sorting numbers with a specific range and base. I have n numbers in the range of 1-n^10 and the base for the radix sort is n/log n. I have tried ...
43 views

I am a little confused by the complexity proof of Radix Sort. For counting sort, the complexity reported is $O(n+R)$, where $n$ is the number of items and $R$ is the range. But this is not entirely ...
62 views

### Can radix sort reach exponential time complexity?

For example, assume the input array is $$[121212,212121]$$ Say we are in base 10, so count sort will work in $O(n)$ time. We have 6 iterations which is approximately $n^2$. Is this a worst case ...
15 views

### Analysis of Radix sort of $n$ $b$ bit numbers

I was reading radix sort in Introduction to Algorithms by CLRS . And it gave the following Lemma with its analysis I understood the proof of the Lemma but confused on the part where they try to ...
32 views

### Radix sort slower than Quick sort?

I would like to demonstrate that sometime radix-sort is better than quick-sort. In this example I am using the program below: ...
78 views

### Quick Sort vs Radix Sort

In an coding exam, I was once asked this question: Assuming that you are only sorting Integers in ascending order, which algorithm do you use when you want to prioritize speed the most, but you ...
286 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 "...
71 views

### What is the time and space complexity for radix search tree

What is the time and space complexity for radix search tree in this research https://www.researchgate.net/publication/314799182_Novel_Approach_for_Arabic_Spell-Checker_Based_on_Radix_Search_Tree
101 views

49 views

### Find fastest sort for given range of numbers

I encountered a question from a test that I cant understand the answer given a range of numbers $[0...(logn)^{logn}-1]$ we need to find the quickest sort available and give his running time now ...
216 views

### How to sort an array $A[1..i..n]$ where $A[i] \in \{1,2,..,n^5 \}$ in $\Theta (n)$ time?

I need to write a sorting algorithm which will sort an array $A[1..n]$, $1 \le i \le n$ such that $A[i] \in \{1,2,..,n^5 \}$, all numbers are positive integers in $\Theta (n)$ time. The solution must ...
761 views

### Why does radix sort work?

I understand how radix sort works and how to implement it, but I don't understand why it works. Are there any underlying mathematical or logical principles that it relies on?
82 views

### Radix sort with 2 digit elements [closed]

How can we prove that radix sort correctly sorts an array of 2 elements with 2 digits each ?
154 views

### O(n) sorting array by value - get indexes

I am in search of a linear-time sorting algorithm that is capable of returning an array B of indices A, sorted on the value of the corresponding element of A. For example: Input = [2, 6, 8, 9, 1, 7, ...
371 views

### Fastest in-place sorting algorithm for Epochtime

I need to sort a lot of rows (from 1GB to 3GB) by EpochTime (a single value of every row). What is the fastest in-place sorting algorithm for this task? Radix Sort? I would like the fastest sorting ...
822 views

### Which pass do you look at for Radix Sort stability?

I know this is a fairly poorly worded question, but I can't think of a better way to phrase it in the title. So in Radix Sort, you go digit by digit from least significant to most significant, and ...
177 views

### How do I sort these elements in O(n) time?

So let's say I have an array of elements where each of the values can range from 0 to $n^2-1$. I'm trying to make an algorithm to sort this array in O(n) running time and I was thinking of using radix ...
927 views

### Radix sort and changing bases

I have recently learned about radix sort. I am aware that you can change the base of the numbers you need to sort but I don't really understand why this is good for the radix sort. Radix sort runtime ...
197 views

Is it better to use comparison or radix sort to sort a long sequences of java int array? I know that I should probably use mergesort (NlogN) for comparison sort, since it is one of the fastest and ...
3k views

2k views

### Is radix sort really O(n) for sorting 32 bit integers?

I was trying to analyze radix sort in terms of time and space. Assume that we are given $n$ 32-bit integers which we would want to sort by looking at the least significant digits first. $k$ is the ...
1k views

### Sorting in O(n) time in a finite domain

I've been stuck with this problem for 2 weeks. Any idea of how to aproach it?. Let $L$ be a list of $n$ different integer numbers, assume that the elements of $L$ are in the range $[1,750]$. Design ...
Radix sort is theoretically very fast when you know that the keys are in a certain limited range, say $n$ values in the range $[0\dots n^k -1]$ for example. If $k<\lg n$ you just convert the ...