Sorting Algorithms Questions and Answers

Q: The worst case running times of Insertion sort, Merge sort and Quick sort, respectively, are:

The worst case times are \(\Theta(n^{2})\), \(\Theta(n\log n)\), and \(\Theta(n^{2})\).Insertion sort: on reverse-sorted input each element shifts past all the earlier ones, \(1 + 2 + \cdots + (n-1) = \Theta(n^{2})\). Merge sort: it always halves the array and merges in linear time, \(\Theta(n\log n)\) in every case. Quick sort: if the pivot is always the smallest or largest element (for example the first element of sorted input), each partition removes only one element, giving \(\Theta(n^{2})\).Quick sort's \(\Theta(n\log n)\) is its average case, which is the trap in the other options; insertion sort's worst case is never \(n\log n\).

Q: Assume that the algorithms considered here sort the input sequences in ascending order. If the input is already in ascending order, which of the following are TRUE?I. Quicksort runs in \(\Theta(n^{2})\) timeII. Bubblesort runs in \(\Theta(n^{2})\) timeIII. Mergesort runs in \(\Theta(n)\) timeIV. Insertion sort runs in \(\Theta(n)\) time

The true statements are I and IV only.I: the standard quicksort picks the first (or last) element as pivot. On sorted input that pivot is the smallest (or largest) element, every partition is maximally unbalanced, and the running time is \(\Theta(n^{2})\).IV: insertion sort compares each new element only with its left neighbour, finds it already in place and moves on, so sorted input takes \(\Theta(n)\).II is not taken as true: bubble sort with the usual check for a pass with no swaps stops after one pass over sorted input, \(\Theta(n)\); the key assumes this standard version, since a bubble sort without the check would take \(\Theta(n^{2})\). III is false: merge sort always splits and merges fully, so it takes \(\Theta(n\log n)\) on any input, never \(\Theta(n)\).

Q: The number of times swap function called for the selection sort on an array with N numbers is :

Selection sort calls swap N-1 times.Selection sort makes N-1 passes. In each pass it scans the unsorted part to find the smallest element and then swaps it into the first unsorted position, one swap per pass. After N-1 passes the last element is automatically in place. (An implementation that skips swapping an element with itself can do fewer, but the standard count is N-1.)\(N^{2}\) is the order of the number of comparisons, about N(N-1)/2, not swaps. N log N is the cost of efficient sorts such as merge sort, and log N is far too few to move N elements into place.

Q: The best/worst case time complexity of Bubble sort is :

Bubble sort is O(n) in the best case and O(\(n^{2}\)) in the worst case.Bubble sort with the usual 'swapped' flag stops as soon as a pass makes no swaps. On an already sorted array the first pass of n-1 comparisons makes no swaps, so the best case is O(n). On a reverse-sorted array every pass swaps, and about n(n-1)/2 comparisons and swaps are needed, so the worst case is O(\(n^{2}\)).O(n log n) is the complexity of merge sort and of heap sort, not of bubble sort, which rules out options B, C and D.

Q: Which of the following sorting does not have worst case running time of O(n\(^{2}\)) ?

Merge sort (printed 'Merger sort') does not have an O(n\(^{2}\)) worst case.Merge sort always splits the list into halves and merges them in linear time, so its running time is O(n log n) in every case, including the worst.Quick sort is O(n log n) on average but O(n\(^{2}\)) in the worst case, when pivots split the list very unevenly, as with already sorted input and a first-element pivot. Insertion sort and bubble sort are O(n\(^{2}\)) in the worst case, on reverse-sorted input.

Q: Which of the following sorting algorithms is based on the concept of repeatedly finding the minimum element ?

The algorithm is Selection Sort.Selection sort repeatedly finds the minimum element of the unsorted part and swaps it into the next position of the sorted part, so after k passes the first k elements are in final order.Quick sort partitions around a pivot, bubble sort swaps adjacent out-of-order pairs, and merge sort divides and merges, so none of them works by repeatedly selecting the minimum.

Q: In which of the following cases does the worst-case time complexity of Quick Sort occur ?

Quick sort's worst case occurs when the pivot element is the smallest or largest element.If the pivot is always the minimum or maximum, each partition separates only one element, so there are n levels of partitioning and the running time becomes \(O(n^2)\).An already sorted array causes this only when the first or last element is chosen as pivot, so it is a special case of option C rather than the general condition. A randomly chosen pivot makes the worst case very unlikely.

Q: What is the best-case time complexity for the Bubble Sort algorithm ?

The best-case time of bubble sort is O(n).With the usual optimisation, bubble sort stops when a pass makes no swaps. If the array is already sorted, the first pass of n - 1 comparisons finds no swaps, so it finishes in linear time.\(O(n^2)\) is its average and worst case, \(O(n \log n)\) belongs to efficient sorts such as merge sort, and O(log n) is binary search.

Q: What is the time complexity of Merge Sort in the worst case ?

Merge sort's worst case is O(n log n).Merge sort always splits the array in half (about \(\log_2 n\) levels) and merges each level in O(n) time, whatever the input order, so its best, average and worst cases are all \(O(n \log n)\).\(O(n^2)\) is the worst case of quick sort and simple sorts, O(n) the best case of bubble or insertion sort, and O(log n) binary search.

Q: Which of the following sorting algorithms has the best time complexity in the worst case ?

The best worst-case complexity is Merge Sort.Merge sort runs in \(O(n \log n)\) even in the worst case, because it always divides the array evenly.Quick sort averages \(O(n \log n)\) but degrades to \(O(n^2)\) with bad pivots, and bubble sort and selection sort are \(O(n^2)\) in the worst case.Heap sort also has a worst case of \(O(n \log n)\), but it is not among the options.

The worst case running times of Insertion sort, Merge sort and Quick sort, respectively, are:

A.\(\Theta(n\log n)\), \(\Theta(n\log n)\), and \(\Theta(n^{2})\)
B.\(\Theta(n^{2})\), \(\Theta(n^{2})\), and \(\Theta(n\log n)\)
C.\(\Theta(n^{2})\), \(\Theta(n\log n)\), and \(\Theta(n\log n)\)
D.\(\Theta(n^{2})\), \(\Theta(n\log n)\), and \(\Theta(n^{2})\)

Exam Year(s)

GATE CS - 2016,

Answer: D

The worst case times are \(\Theta(n^{2})\), \(\Theta(n\log n)\), and \(\Theta(n^{2})\).

Insertion sort: on reverse-sorted input each element shifts past all the earlier ones, \(1 + 2 + \cdots + (n-1) = \Theta(n^{2})\). Merge sort: it always halves the array and merges in linear time, \(\Theta(n\log n)\) in every case. Quick sort: if the pivot is always the smallest or largest element (for example the first element of sorted input), each partition removes only one element, giving \(\Theta(n^{2})\).

Quick sort's \(\Theta(n\log n)\) is its average case, which is the trap in the other options; insertion sort's worst case is never \(n\log n\).

Discuss in Forum

Assume that the algorithms considered here sort the input sequences in ascending order. If the input is already in ascending order, which of the following are TRUE?

I. Quicksort runs in \(\Theta(n^{2})\) time
II. Bubblesort runs in \(\Theta(n^{2})\) time
III. Mergesort runs in \(\Theta(n)\) time
IV. Insertion sort runs in \(\Theta(n)\) time

A.I and II only
B.I and III only
C.II and IV only
D.I and IV only

Exam Year(s)

GATE CS - 2016,

Answer: D

The true statements are I and IV only.

I: the standard quicksort picks the first (or last) element as pivot. On sorted input that pivot is the smallest (or largest) element, every partition is maximally unbalanced, and the running time is \(\Theta(n^{2})\).

IV: insertion sort compares each new element only with its left neighbour, finds it already in place and moves on, so sorted input takes \(\Theta(n)\).

II is not taken as true: bubble sort with the usual check for a pass with no swaps stops after one pass over sorted input, \(\Theta(n)\); the key assumes this standard version, since a bubble sort without the check would take \(\Theta(n^{2})\). III is false: merge sort always splits and merges fully, so it takes \(\Theta(n\log n)\) on any input, never \(\Theta(n)\).

Discuss in Forum

The number of times swap function called for the selection sort on an array with N numbers is :

A.\(N^{2}\)
B.N log N
C.log N
D.N-1

Exam Year(s)

MH SET - 2018, SET Exam - 2018,

Answer: D

Selection sort calls swap N-1 times.

Selection sort makes N-1 passes. In each pass it scans the unsorted part to find the smallest element and then swaps it into the first unsorted position, one swap per pass. After N-1 passes the last element is automatically in place. (An implementation that skips swapping an element with itself can do fewer, but the standard count is N-1.)

\(N^{2}\) is the order of the number of comparisons, about N(N-1)/2, not swaps. N log N is the cost of efficient sorts such as merge sort, and log N is far too few to move N elements into place.

Discuss in Forum

The best/worst case time complexity of Bubble sort is :

A.O(n)/ O(\(n^{2}\))
B.O(n)/ O(n log n)
C.O(n log n)/O(n log n)
D.O (n log n)/ O(\(n^{2}\) log n)

Exam Year(s)

MH SET - 2018, SET Exam - 2018,

Answer: A

Bubble sort is O(n) in the best case and O(\(n^{2}\)) in the worst case.

Bubble sort with the usual 'swapped' flag stops as soon as a pass makes no swaps. On an already sorted array the first pass of n-1 comparisons makes no swaps, so the best case is O(n). On a reverse-sorted array every pass swaps, and about n(n-1)/2 comparisons and swaps are needed, so the worst case is O(\(n^{2}\)).

O(n log n) is the complexity of merge sort and of heap sort, not of bubble sort, which rules out options B, C and D.

Discuss in Forum

Which of the following sorting does not have worst case running time of O(n\(^{2}\)) ?

A.Merger sort
B.Quick sort
C.Insertion sort
D.Bubble sort

Exam Year(s)

MH SET - 2025, SET Exam - 2025,

Answer: A

Merge sort (printed 'Merger sort') does not have an O(n\(^{2}\)) worst case.

Merge sort always splits the list into halves and merges them in linear time, so its running time is O(n log n) in every case, including the worst.

Quick sort is O(n log n) on average but O(n\(^{2}\)) in the worst case, when pivots split the list very unevenly, as with already sorted input and a first-element pivot. Insertion sort and bubble sort are O(n\(^{2}\)) in the worst case, on reverse-sorted input.

Discuss in Forum

Which of the following sorting algorithms is based on the concept of repeatedly finding the minimum element ?

A.Quick Sort
B.Selection Sort
C.Bubble Sort
D.Merge Sort

Exam Year(s)

Tripura Public Service Commission - 2025,

Answer: B

The algorithm is Selection Sort.

Selection sort repeatedly finds the minimum element of the unsorted part and swaps it into the next position of the sorted part, so after k passes the first k elements are in final order.

Quick sort partitions around a pivot, bubble sort swaps adjacent out-of-order pairs, and merge sort divides and merges, so none of them works by repeatedly selecting the minimum.

Discuss in Forum

In which of the following cases does the worst-case time complexity of Quick Sort occur ?

A.When the pivot element is chosen randomly
B.When the array is already sorted
C.When the pivot element is the smallest or largest element
D.None of the above

Exam Year(s)

Tripura Public Service Commission - 2025,

Answer: C

Quick sort's worst case occurs when the pivot element is the smallest or largest element.

If the pivot is always the minimum or maximum, each partition separates only one element, so there are n levels of partitioning and the running time becomes \(O(n^2)\).

An already sorted array causes this only when the first or last element is chosen as pivot, so it is a special case of option C rather than the general condition. A randomly chosen pivot makes the worst case very unlikely.

Discuss in Forum

What is the best-case time complexity for the Bubble Sort algorithm ?

A.O(n)
B.O(n logn)
C.O(n^2)
D.O(log n)

Exam Year(s)

Tripura Public Service Commission - 2025,

Answer: A

The best-case time of bubble sort is O(n).

With the usual optimisation, bubble sort stops when a pass makes no swaps. If the array is already sorted, the first pass of n - 1 comparisons finds no swaps, so it finishes in linear time.

\(O(n^2)\) is its average and worst case, \(O(n \log n)\) belongs to efficient sorts such as merge sort, and O(log n) is binary search.

Discuss in Forum

What is the time complexity of Merge Sort in the worst case ?

A.O(n)
B.O(n log n)
C.O(n^2)
D.O(log n)

Exam Year(s)

Tripura Public Service Commission - 2025,

Answer: B

Merge sort's worst case is O(n log n).

Merge sort always splits the array in half (about \(\log_2 n\) levels) and merges each level in O(n) time, whatever the input order, so its best, average and worst cases are all \(O(n \log n)\).

\(O(n^2)\) is the worst case of quick sort and simple sorts, O(n) the best case of bubble or insertion sort, and O(log n) binary search.

Discuss in Forum

10.

Which of the following sorting algorithms has the best time complexity in the worst case ?

A.Quick Sort
B.Merge Sort
C.Bubble Sort
D.Selection Sort

Exam Year(s)

Tripura Public Service Commission - 2025,

Answer: B

The best worst-case complexity is Merge Sort.

Merge sort runs in \(O(n \log n)\) even in the worst case, because it always divides the array evenly.

Quick sort averages \(O(n \log n)\) but degrades to \(O(n^2)\) with bad pivots, and bubble sort and selection sort are \(O(n^2)\) in the worst case.

Heap sort also has a worst case of \(O(n \log n)\), but it is not among the options.

Discuss in Forum

Loading…

Topics

Other Subjects

Tags: Sorting Algorithms Questions and Answers || Sorting Algorithms MCQ Questions and Answers || Sorting Algorithms GK Questions and Answers || Sorting Algorithms GK MCQ Questions || Sorting Algorithms Multiple Choice Questions and Answers || Sorting Algorithms GK || GK on Sorting Algorithms || Data Structures and Algorithms Questions and Answers || Data Structures and Algorithms MCQ Questions and Answers || Data Structures and Algorithms GK Questions and Answers || GK on Data Structures and Algorithms

Sorting Algorithms Questions and Answers

Topics

Other Subjects

About Us

Stay informed about all important Dates & Notifications