Home > Uncategorized > Best case and worst case situation of Sorting algorithms

Best case and worst case situation of Sorting algorithms

Insertion sort :

Best case: Inputs are already sorted in ascending order.

Worst case: Inputs are sorted in Descending order.

Merge Sort:

Best case: Both increasing and decreasing order will lead to best case in merge sort.

Worst case: Inputs are sorted in not increasing or decreasing fashion. Exactly big and small values should be interwoven so that in each marging state more comparison is needed. Ex: 100, 0, 101,1,102,2,103,3,104,4 … such list will have the maximum comparison in each merging.

Quick Sort:

In randomization is not used and the pivot is chosen from the last element the worst case is when the input are totally sorted (either ascending or descending). But here the Complexity depends how pivot are chosen.


Best case when the element are sorted in Descending order and worst case when elements are sorted in ascending order.

Hope I am correct. Please let me know if I am incorrect.

Prosunjit Biswas

CS UTSA.

Advertisements
Categories: Uncategorized
  1. No comments yet.
  1. No trackbacks yet.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: