Sorting(Algorithms)

Question

The complexity of comparison based sorting algorithm is (nlogn) .How?

Answer 1

https://youtu.be/z9EWVOyvcVM , see this video by Gatebook . It is beautifully explained how comparison based sorting algorithms have nlogn time complexity  

Answer 2

@_Madhuri

Comparison based sorting algorithm time complexity :

In comparison based sorting, elements of an array are compared with each other to find the sorted array.

 

Best case time complexity:

n when array is already sorted.

 

Worst case:

when the array is reverse sorted.

 

Best, average and worst case time complexity:

n^2 which is independent of distribution of data.

 

@@ https://www.youtube.com/watch?v=WffUZk1pgXE 

 

1. https://gateoverflow.in/85292/comparison-based-sort 

 

2. https://gateoverflow.in/84830/gate-cse-1990-question-3-v 

 

3. https://gateoverflow.in/1026/gate-cse-2004-question-29

 

 

Comments

this is for bubble sort when array is sorted t.c is order of n

and when array is reverse order t.c is n2.