# How to find examples of best cases for sorting algorithms?

I am asked to give a table of 8 elements that are to be sorted by the following algorithms and to produce their best cases. 1) Selection sort 2) Bubble sort 3) Insertion sort 4) Fusion sort

If I give an already sorted table ex: {1,2,3,4,5,6,7,8} shouldn't it already be the best case for all of them? If I can be considered a best case for each?

• "If I can be considered a best case for each?" What do you mean by that sentence? Please edit your question to clarify. Commented Apr 6, 2019 at 19:24

Bubble sort can "stop early" should the array already be sorted. Other algorithms have their own advantages or applications, but none of the algorithms mentioned in your question - other than bubble sort - can "stop early".

Therefore for any input Insertion & Selection runtime will be $$\Omega (n^2)$$, and Mergesort $$\Omega(nlog(n))$$, so the order of elements doesn't matter at all.

$$\bullet$$ If you perform bubble sort on an already sorted array, the algorithm can stop when not performing any swaps, and run at $$O(n)$$

$$\bullet$$ Merge sort (to which you refer as 'fusion sort' from some reason) is the only algorithm that requires $$O(nlog(n))$$ rather than $$O(n^2)$$

$$\bullet$$ Insertion sort is useful when receiving the array online (one element at a time) and maintaining it sorted. Its noteworthy that since you maintain a sorted array, new elements can be inserted via binary search, which make the insertion sort perform $$O(nlog(n))$$ comparisons, but still cost $$O(n^2)$$ due to moving elements.

$$\bullet$$ Selection sort is very easy to implement and intuitive to explain

• By the way, you can use \log to denote $\log$ such as in $O(n\log n)$. Commented Apr 6, 2019 at 19:37
• It may not be a bad idea to add a linear check if the array is sorted in any step (which can make both insertion and selection also linear in best case), but not sure OP meant modified algorithms. I did not think of a binsearch insertion, that is an insteresting point and i will edit it in. Thanks.
– lox
Commented Apr 6, 2019 at 19:44
• An insertion algorithm that compares the last element in the result array with the new element will run $O(n)$ on $1,2,3,\cdots,n$. (Of course, binary search for insertion is a very interesting variation.) Even if "new elements can be inserted via binary search", that does not make it run in $O(n\log n)$. Binary search reduces the number of comparisons; however, the steps that are needed for the actual insertion take $\Theta(n^2)$ in average. Commented Apr 6, 2019 at 19:52
• You're right. edited it. No, i didn't implement any variation of insertion sort
– lox
Commented Apr 6, 2019 at 19:56
• Upvoted, although this answer still misses some finer (or pedantic) details. Commented Apr 7, 2019 at 20:15