Merge sort has a reliable workload / speed regardless of data size or the 'sortedness' of the data. It has good worst-case behaviour, but you can find plenty of other algorithms with a better best-case behaviour. Bubble sort actually has the best possible best-case sort behaviour (for a sorted list), because if the list is already sorted then nothing is changed and you've only needed to iterate through the list once to find that out.

If you want a "better" algorithm that is more comparable to bubble sort, then quick sort (or its variants) are a more appropriate comparison. Quick sort is sort of like bubble sort, but skips a lot of intermediate steps (you switch a value with another value without switching all the intermediate values between). However, quick sort performs fairly badly on a sorted list, and can take of the order of n^2 operations to 'sort' a sorted list of size n.

Merge sort has a reliable workload / speed regardless of data size or the 'sortedness' of the data. It has good worst-case behaviour, but you can find plenty of other algorithms with a better best-case behaviour. Bubble sort actually has the best possible best-case sort behaviour (for a sorted list), because if the list is already sorted then nothing is changed and you've only needed to iterate through the list once to find that out.

If you want a "better" algorithm that is more comparable to bubble sort, then quick sort (or its variants) are a more appropriate comparison. Quick sort is sort of like bubble sort, but skips a lot of intermediate steps (you switch a value with another value without switching all the intermediate values between). However, quick sort performs fairly badly on a sorted list, and can take of the order of n^2 operations to 'sort' a sorted list of size n.

Dear Dr. Qaim Mehdi Rizvi,

While Bubble Sort algorithm is simple but this algorithm is highly inefficient and is rarely used for research and designs. however this algorithm is popular in education. A slightly better variant, I may suggest you for using Cocktail Sort algorithm.

(1) Merge-sort needs an auxiliary array (extra space) to sort and cause more memory access (2) If the data is already sorted then Bubble-sort will not move any elements. Therefore, Bubble-sort may perform better for small data-set. However, Merge-sort is O(n log n) and Bubble Sort is O(n*n) , therefore for any reasonable size data Merge-sort will outperform Bubble sort.

.

1) introduce the difference between worst case and average complexity

2) play around with MergeSort, HeapSort, BubbleSort and QuickSort : code them properly, identify the best and worst case for each, work with large samples of random lists for average case computation, report and analyze distributions ; do this for various list sizes

3) compare with theoretical big O's and discuss !

Time complexities :

Quick sort

Worst case = O(n^2)

Average case = O(n log n)

Merge Sort, HeapSort

Worst case = O(n log n)

Average case = O(n log n)

Bubble sort

Worst case = O(n^2)

Average case = O(n^2)

Space complexities

O(1), except MergeSort which is O(n) as you pointed out

(and of course, one of the fun parts is to realize how hard it is to sample such large sets as the set of permutations even for moderate n values ...)

.

'Bubble sort' is certainly interesting as an educational tool. However, in practice, the standard variant of BS is never the best choice. Indeed, for large N, it becomes unworkable because of O(N²) behavior, whereas for small N, it will not perform better than, for example, a simple 'Shell sort', which has a comparatively similar code size and which can compete with the best methods for moderate values of N (say N < 50).

The so-called 'Rabbits' and 'Turtles' may help in understanding the main features of BS and its drawback. 'Rabbits' are elements that have a high value and that are located near the top of the original list. These elements are not an issue because the BS algorithm will force them to move down very quickly towards the bottom of the list at their correct final position. 'Turtles', on the other hand, are elements that have a small value and that are located near the bottom of the original list. These elements will be moved towards the top of the list but, unfortunately, very very slowly and are thus the source of the main drawback of the algorithm.

Of course, variants of BS aim at killing these nasty 'Turtles'. For example, 'Cocktail Sort' (mentioned above by @Afaq Ahmad) alternates the working direction of the standard BS procedure so that, once every two passes of the loop, 'Turtles' become 'Rabbits' and vice versa. Unfortunately, 'Cocktail sort' is only a slight improvement of the standard BS..

On the other hand, 'Comb Sort' is a remarkable variant of BS that can compete with the best methods for moderate values of N. The description of this variant is as follows: Instead of comparing (and perhaps swapping) two adjacent elements, 'Comb sort' does this same operation but between two elements that are far apart. In other words, instead of using a fine comb with a gap = 1 (as BS does), this variant uses a coarse comb with a gap > 1. Then, at each iteration, the comb becomes finer and finer (the gap being progressively shrunk by a factor of 1.3) so that the final pass is done using a gap = 1 (same as BS). Interestingly, 'Comb sort' is only a small modification of the original BS, yet the improvement is significant so that this variant can be used instead of BS for small N.

Just a tip for people using the C function qsort() : if your compare-function is nothing but an if statement comparing two elements, making the compare-function 'inline' (C++) will boost the performance by 30%. As mentioned, the average performance will still be O(n log n).

the issue is the constants that go with any "big_O" asymptotics

it is clearly possible for (small constant) * N^2 < (big constant) N * log N when N is small enough

in a related issue, there is a marvelous paper showing that the median of a set can be computed in linear time, using a complicated data structure and sorting of small subsets of the data (scho:nhage, paterson and pippenger were the authors, i think), and i decided to figure out when the algorithm would be faster than just sorting them all and choosing the middle one (which is clearly at least N*log N asymptotically)

it turned out that if you were trying to find the median of a set of more than about 75 million elements, this algorithm was better

so beware the constants

This is Insertion sort not Bubble sort, though the difference is pretty pedantic, as measured (hence the experimental error spikes) in MatLab. So the break-even seems to be at about 2000, FOR THIS SYSTEM

Dear ALL, There exist better algorithm than Bubble sort algorithm. Many languages have built-in sort functions. We should apply the better tact using data structure and algorithms.

This seems to be an artifact of the multi-user machine. If I repeat, I get the same behaviour, but with the spikes in different places. For each I computed the two times, then moved to the next N.