CODEWITHSUNDEEP
algorithmmatlabsortingbig-o
Vladamir
Vladamir

Reputation: 247

Matlab - Sorting algorithms

I have been looking at various sorting algorithms such as merge, bubble, quick and bucket type sorts in Matlab and have a few questions. It states that the running time for insertion sort, bubble sort and quick sort are O(n^2), while the running times for merge and bucket are O(nlog(n)). I am wondering why, if the last two are simply faster, is the reason for using any of the first 3. Are they faster if the list is more sorted / less sorted, bigger / smaller ect, or is there some other reason?

Upvotes: 0

Views: 1406

Answers (2)

rcgldr
rcgldr

Reputation: 28826

I'm not sure how this would apply to Matlab, as I don't know how it's sorting algorithms are implemented.

Other than radix sort which is fastest in cases like sorting an array of integers, the average time for quick sort versus merge sort on near random data is close, but merge sort needs O(n) space. Merge sort is stable (retains the order of equal elements), while quick sort is not stable.

Quick sort does more compares, but fewer moves than merge sort. Which is faster is affected by this. If using a user defined function for the compare, merge sort will typically be a bit faster.

On a processor with 16 registers, such as a PC in 64 bit mode, then a 4-way merge sort will be a bit faster than a quick sort or a standard 2-way merge sort. A 4-way merge sort does 1.5 x compares, but 0.5 x moves, so the total number of basic operations is the same, but the compares tend to be a bit more cache friendly, so 4-way is a bit faster. For large arrays of random integers, the difference between any of these sort methods is normally less than 10%, so there's not much of a practical difference.

Multi-threading on a multi-core processor makes a big difference. I bench marked sorting an array of 16 million pseudo random 32 bit integers, and a four thread (bottom up / iterative) merge sort was about 3 times as fast as a single thread (bottom up / iterative) merge sort (0.5 seconds versus 1.5 seconds). The main benefit occurs due to how much of the sorting occurs within each core's local cache.

Upvotes: 0

Matt Timmermans
Matt Timmermans

Reputation: 59184

Insertion sort is used for arrays that are known to be very small, since it's often the fastest in that case.

Quick sort is used in practice a lot, because it has expected N log N time, is quite fast in most cases, and works in-place on arrays -- you don't need to allocate a backup array.

Merge sort is used for linked lists, and sometimes for arrays when you really need O(N log N) time OR you really need a stable sort. (quick sort is not stable). Using merge sort for arrays requires you to allocate a spare array that you can use as temporary storage during merges.

Bucket sort is only applicable for certain types of data, so it's not that common, but you can use it to good effect when the data fits. It's also normally considered O(N)

Heap sort is used on arrays when you don't need a stable sort and you really need O(N log N) time. It's not stable either, and it's slower than quick sort in most cases.

Oh, and as for bubble sort... well, nobody uses bubble sort

Upvotes: 3

Related Questions