Sorting Algorithms Questions and Answers

Q: What is the time complexity of the Quick Sort algorithm in the average case ?

Quick sort's average case is O(n log n).Each partition step does linear work. With reasonably balanced splits the recursion is about log n levels deep, giving n log n in total, and averaged over random inputs or random pivots the expected number of comparisons is about 1.39 n log2 n.\(O(n^{2})\) is quick sort's worst case, when the pivot is always the smallest or largest element, for example on sorted input with a first-element pivot. O(n) is too fast for any comparison sort, and O(log n) is the depth of the recursion, not the total work.

Q: What is the space complexity of merge sort algorithm ?

The space complexity of merge sort is O(n).The standard array merge sort copies the two halves into temporary arrays to merge them, which needs auxiliary space proportional to n. The recursion stack adds only O(log n), so the total is dominated by the O(n) buffer.O(1) extra space is achieved by in-place sorts such as heapsort. O(log n) is roughly what quick sort needs for its recursion. O(n log n) is merge sort's running time, not its space.

Q: What is the worst-case time complexity of insertion sort ?

The worst-case time of insertion sort is \(O(n^{2})\).In the worst case, a reverse-sorted array, the i-th element has to be shifted past all i - 1 elements before it:\[ 1 + 2 + \cdots + (n-1) = \frac{n(n-1)}{2} \]That number of comparisons and shifts grows as n squared.O(n) is insertion sort's best case, on input that is already sorted. O(n log n) is the bound for merge sort or heapsort, and O(log n) is a single binary search, not a full sort.

Q: Consider the following array. 2332456972738997 Which algorithm out of the following options uses the least number of comparisons (among the array elements) to sort the above array in ascending order ?

The algorithm with the fewest comparisons is insertion sort.The array is already in ascending order. Insertion sort compares each new element only with the one before it, finds it already in place, and moves on, so it uses just n - 1 = 7 comparisons.Selection sort always makes n(n - 1)/2 = 28 comparisons. Merge sort makes about n log n comparisons regardless of order. Quicksort with the last element as pivot hits its worst case on sorted input, also about 28 comparisons.

Q: Which sorting algorithm has worst-case time complexity of O(n2) ?

The algorithm with worst-case time O(n2) is Quick Sort.Quick sort is O(n log n) on average, but if the pivot chosen is always the smallest or largest element (for example, taking the first element of an already sorted array), each partition removes only one element and the work grows as n + (n - 1) + ... + 1, which is O(n2).Merge sort and heap sort are O(n log n) even in the worst case. Counting sort is not a comparison sort and runs in O(n + k), where k is the range of the keys.

Q: Given a set of n integers the worst case time complexity of quick sort is

The worst case of quick sort is \(\theta(n^{2})\).The worst case arises when every pivot is the smallest or largest element, for example on already sorted input with the first element as pivot. Each partition then removes only the pivot, and the comparisons add up to \((n-1) + (n-2) + \cdots + 1 = \frac{n(n-1)}{2}\).\(\theta(n \log n)\) is the average and best case, when partitions are balanced. \(\theta(n)\) is too small for any comparison sort, and \(\theta(n^{2} \log n)\) is larger than quick sort ever needs.

11.

What is the time complexity of the Quick Sort algorithm in the average case ?

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

Exam Year(s)

Tripura Public Service Commission - 2026,

Answer: B

Quick sort's average case is O(n log n).

Each partition step does linear work. With reasonably balanced splits the recursion is about log n levels deep, giving n log n in total, and averaged over random inputs or random pivots the expected number of comparisons is about 1.39 n log₂ n.

\(O(n^{2})\) is quick sort's worst case, when the pivot is always the smallest or largest element, for example on sorted input with a first-element pivot. O(n) is too fast for any comparison sort, and O(log n) is the depth of the recursion, not the total work.

Discuss in Forum

12.

What is the space complexity of merge sort algorithm ?

A.O(1)
B.O(log n)
C.O(n)
D.O(n log n)

Exam Year(s)

Tripura Public Service Commission - 2026,

Answer: C

The space complexity of merge sort is O(n).

The standard array merge sort copies the two halves into temporary arrays to merge them, which needs auxiliary space proportional to n. The recursion stack adds only O(log n), so the total is dominated by the O(n) buffer.

O(1) extra space is achieved by in-place sorts such as heapsort. O(log n) is roughly what quick sort needs for its recursion. O(n log n) is merge sort's running time, not its space.

Discuss in Forum

13.

What is the worst-case time complexity of insertion sort ?

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

Exam Year(s)

Tripura Public Service Commission - 2026,

Answer: C

The worst-case time of insertion sort is \(O(n^{2})\).

In the worst case, a reverse-sorted array, the i-th element has to be shifted past all i - 1 elements before it:

\[ 1 + 2 + \cdots + (n-1) = \frac{n(n-1)}{2} \]

That number of comparisons and shifts grows as n squared.

O(n) is insertion sort's best case, on input that is already sorted. O(n log n) is the bound for merge sort or heapsort, and O(log n) is a single binary search, not a full sort.

Discuss in Forum

14.

Consider the following array.

Which algorithm out of the following options uses the least number of comparisons (among the array elements) to sort the above array in ascending order ?

A.Selection sort
B.Merge sort
C.Insertion sort
D.Quicksort using the last element as pivot

Exam Year(s)

Tripura Public Service Commission - 2025,

Answer: C

The algorithm with the fewest comparisons is insertion sort.

The array is already in ascending order. Insertion sort compares each new element only with the one before it, finds it already in place, and moves on, so it uses just n - 1 = 7 comparisons.

Selection sort always makes n(n - 1)/2 = 28 comparisons. Merge sort makes about n log n comparisons regardless of order. Quicksort with the last element as pivot hits its worst case on sorted input, also about 28 comparisons.

Discuss in Forum

15.

Which sorting algorithm has worst-case time complexity of O(n²) ?

A.Merge Sort
B.Quick Sort
C.Heap Sort
D.Counting Sort

Exam Year(s)

Tripura Public Service Commission - 2026,

Answer: B

The algorithm with worst-case time O(n²) is Quick Sort.

Quick sort is O(n log n) on average, but if the pivot chosen is always the smallest or largest element (for example, taking the first element of an already sorted array), each partition removes only one element and the work grows as n + (n - 1) + ... + 1, which is O(n²).

Merge sort and heap sort are O(n log n) even in the worst case. Counting sort is not a comparison sort and runs in O(n + k), where k is the range of the keys.

Discuss in Forum

16.

Given a set of n integers the worst case time complexity of quick sort is

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

Exam Year(s)

Tripura Public Service Commission - 2026,

Answer: C

The worst case of quick sort is \(\theta(n^{2})\).

The worst case arises when every pivot is the smallest or largest element, for example on already sorted input with the first element as pivot. Each partition then removes only the pivot, and the comparisons add up to \((n-1) + (n-2) + \cdots + 1 = \frac{n(n-1)}{2}\).

\(\theta(n \log n)\) is the average and best case, when partitions are balanced. \(\theta(n)\) is too small for any comparison sort, and \(\theta(n^{2} \log n)\) is larger than quick sort ever needs.

Discuss in Forum

17.

Suppose there are \(\log_{n}\) sorted lists of n \(\log_{n}\) elements each. The time complexity of producing a sorted list of all these elements is (use heap data structure)

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

Exam Year(s)

UGC NET - 2012,

Answer: A

The key, option A, takes the lists to be log n in number and n divided by log n in length, so that the total number of elements is n. This is read from the key, since as printed the stem shows 'n log n' and not the quotient. With the heap method the merge keeps one element from each of the k = log n lists in a heap and removes the smallest each time. Each of the n steps costs \(O(\log k)\), so the time is \(O(n \log k) = O(n \log \log n)\). The other options, \(\theta(n \log n)\), \(\Omega(n \log n)\) and \(\Omega(n^{3/2})\), are larger than this bound, and a reviewer may wish to check the stem against the key.

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