An ideal sort is an in-place-sort whose additional space requirement is
2015
An ideal sort is an in-place-sort whose additional space requirement is
- A.
O (log2 n)
- B.
O (nlog2 n)
- C.
O (1)
- D.
O (n)
Attempted by 743 students.
Show answer & explanation
Correct answer: C
Answer: O (1)
Explanation: An ideal sort is defined as an in-place sort whose additional space requirement (space used beyond the input storage) is constant. That means the algorithm uses only a fixed amount of extra memory regardless of the input size, which is expressed as O(1).
Examples of algorithms that achieve O(1) additional space: selection sort, insertion sort, and heapsort (ignoring negligible bookkeeping or minimal stack usage).
Why the other choices are incorrect:
O(log n): Some recursive sorts use O(log n) stack space, but that is not constant extra space, so it is not the ideal in-place requirement.
O(n): Algorithms like mergesort (when implemented with an auxiliary array) require linear extra space and therefore are not in-place by the strict definition.
O(n log n): This is a common time complexity for comparison sorts, not a reasonable additional space bound for an in-place algorithm; it is far larger than constant space.