CODEWITHSUNDEEP
sorting
Peter
Peter

Reputation: 1

Efficient Sorting?

I've been looking an answer for this question for sometime now... "What is the most efficient way to sort a million 32-bit integers?"

I feel that Quick sort is the most efficient in sorting.. with an average Runtime of O(n*log n). (with the worst case O(n²))..

But some search results says that Radix sort/Merge sort are efficient for sorting million integers.

Any pointers?

Upvotes: 0

Views: 2999

Answers (4)

Yochai Timmer
Yochai Timmer

Reputation: 49271

Radix is better if for large numbers, especially when you know the range of the numbers.

Calculation fix:

Radix is O(kN) where k is the number of digits in the largest number. (Actually it's about d*k*N where d is the digit base, number of buckets that will be used ... Alphabet = 26, decimal = 10 , binary = 2)

Maxint = 4,294,967,296
32 bits: k = 32 / log(d)

Base 10 Radix:

d*k*n = 10*10*n < nlogn .... 100 < logn ... n > 2^100

Base 2 Radix:

d*k*n = 2*32*n < nlogn .... 64 < logn ... n > 2^64

So for 32bit numbers if you have more than 2^64 numbers n*k*N is better than nlogn

But, if you know that the range will be up to 1024 , and not MAXINT for example:

MaxNumber = 1024

Base 10 Radix:

d*k*n = 10*4*n < nlogn .... 40 < logn ... n > 2^40

Base 2 Radix:

d*k*n = 2*10*n < nlogn .... 20 < logn ... n > 2^20

So for numbers up to 1024 if you have more than 2^20 numbers n*k*N is better than nlogn

Because big O notation discards multiplicative constants on the running time, and ignores efficiency for low input sizes, it does not always reveal the fastest algorithm in practice or for practically-sized data sets, but the approach is still very effective for comparing the scalability of various algorithms as input sizes become large.

Upvotes: 0

BadFileMagic
BadFileMagic

Reputation: 701

Merge sort is O(n log n) in its worst case, so its going to be better than quick sort most of the time. Radix sorts, iirc, are only really useful when each thing being sorted is the same length. Its timed in O(K * N) which is (item length) * (number of items). I don't think I've ever needed to use a Radix sort.

Upvotes: 0

corsiKa
corsiKa

Reputation: 82589

Mergesort is guarenteed to be O(n lg n), but has a higher memory footprint than quick sort.

Quicksort generally runs faster than mergesort, but under ~some~ circumstances it can degrade to quadratic running time.

Radix sort is O(n*r) where r is the length of the numbers.

To determine if radix is better than your chosen lg-n method, do this:

n * r < n * lg (n)
divide by n on both sides
r < lg(n)

We know r is 32 bits

32 < lg(n)

for both sides, take 2^x

2^32 < 2^(lg(n)

2^32 < n

So if n is less than 2^32 (4 billion) then use the lg-n algorithm.

Personally, I'd use quick sort, shuffling it if I have to in order to prevent it from degrading.

Upvotes: 3

Heisenbug
Heisenbug

Reputation: 39194

if you have enough space maybe you can try bucket sort (http://en.wikipedia.org/wiki/Bucket_sort). It's more efficient but requires additional memory to store datas.

Upvotes: 1

Related Questions