• Welcome to Overclockers Forums! Join us to reply in threads, receive reduced ads, and to customize your site experience!

Sorting Algorithms

Overclockers is supported by our readers. When you click a link to make a purchase, we may earn a commission. Learn More.

night8jim

Member
Joined
Feb 24, 2005
Location
UK
Im trying to work something out but cant see why it is the way it is!

I have worked out that a MergeSort has a time complexity of O(n log n)

I have also created a new merge algorithm for 3 splts... which again has given me a time complexity of O(n log n). Im guessing that k splits would still result in O(n log n).

Is there any case when a large split would be better suited?
 
A large split? You mean initially splitting the list up into more chunks?

The reason it's usually split into two chunks is because the resulting comparison during the merge is really easy. Just compare two values and pick one. Going to three chunks means a more complicated merge, to the point where with N chunks you have to find the smallest of N, for which you'd want to do a sort... :) It's kind of self-defeating.

You could argue that more chunks means less iterations of the algorithm, but merge sort can be done in-place and recursing more times really doesn't hurt you.
 
If you are dealing with lists, there is an advantage to using Bucket sort, instead of Merge sort. The big "O" complexity I'm not sure of, but it's a BIG improvement, in that case.

If (getting back to your original question), you can replace Merge or Bucket sort with Counting sort, then there is a HUGE improvement. Counting sort is O(1) - nothing is compared, and nothing is sorted, but you can output the data, in sorted order, from what it makes. Nothing else compares to it, of course, and no, it can't be used for lots of types of data - but when it can, look out!

A fine finesse with Bucket sort, is to use Insertion sort on the data in the individual buckets, keeping them smaller than about 70 items. Insertion sort ROCKS with a small number of items to be sorted - far surpassing Quicksort, Merge sort, or classical Bucket sort.

My favorite all purpose array sorter is Quicksort with Insertion sort handling the smaller sub arrays. A nice improvement over Quicksort alone.
 
Last edited:
Back