Sorting in Data Structure

Bubble sort can have O(n) time complexity if elements are already sorted.
Quick sort and merge sort have time complexity of O(nlogn ) (though worst case complexity of Quicksort is O(n2).
While selection sort always have O(n2 ) complexity. It is pretty obvious because if we look at the logic of selection sort then we select the minimum element at every iteration and replace it with the current position’s element. Whatever be the case, we need to make a complete iteration to find minimum. Thus its complexity cannot be reduced.

Bubble sort can be modified -if all the elements are sorted then no swaps will occur and thus count of swaps=0, which signifies that array is sorted. But in this question there are some elements at the end which are not sorted .So eventually we need to have whole iteration again and again.
Selection sort-It always makes full iteration irrespective of the condition of array.
Quicksort –It will not help as quicksort will choose a random pivot which may disturb sorted part of list L.
Insertion sort-Insertion sort is suitable in this case. If the list is already almost sorted, every time we compare list’s next element it is greater than previous element resulting in no swaps or iteration. Thus no work will be done for sorted part. Only movement for unsorted part would be done.

Insertion, Quick and bubble all have worst case time complexity of O(n2).Only merge sort has the worst case running time of O(nlogn).

In bubble sort once the array becomes sorted say after 2 or 3 iterations, we do not need to make further iterations if we use modified bubble sort.Thus it is best for almost sorted list.
While other algorithms will give O(n2).Quick sort also doesn’t perform well for sorted lists.

Since quicksort requires partitioning using a pivot element thus it is also known as partition exchange sort.

An algorithm is said to be stable if two equal elements appear in the same order in output(sorted objects list) as they appear in input list(unsorted list)
For ex- If we have 5 elements -4, 7, 2, 8, 2
For our understanding, let’s rename sequence as 4, 7, 2(first occurrence), 8, 2(second occurrence)
Then after sorting we will get 2, 2, 4, 7, 8 .But which 2 came first? Which 2 is this? 2(first occurrence) or 2(second occurrence) .If they are in the same order as input ,then such algorithms are called stable algorithm else unstable algorithm.

Quick sort has worst case time complexity as O (n2)

If in any step , no auxiliary space is required to sort the elements then such an algorithm is called in-place sorting algorithm.

All other options name the sorting algorithms which do not require the comparison of elements for sorting.

Heap sort is O(nlogn) even in worst case.