English
Menu

Data Structures and Algorithms

Which sorting algorithm is O(n log n) even in the worst case and sorts with almost no extra memory such as a work array?

  1. AMerge sort
  2. BHeapsort
  3. CQuicksort
Show answer and explanation

Answer: B. Heapsort

Heapsort builds a binary heap inside the array and repeatedly swaps the maximum at the root with the last element and shrinks the heap, so it runs in O(n log n) even in the worst case and needs only a constant amount of extra memory. Merge sort is also O(n log n) in the worst case, but on an array it needs a work area proportional to n. Quicksort is O(n log n) on average and fast in practice, but depending on the pivot choice and the data it can degrade to O(n²). Note that heapsort compares elements that are far apart, so its cache efficiency is poor, and it is not stable.

  • A. It is O(n log n) in the worst case, but on an array it needs a work area proportional to n.
  • B. Correct. It is O(n log n) even in the worst case and sorts within the array itself.
  • C. It is O(n log n) on average but O(n²) in the worst case.
Practice this topic Back to topic

Related calculators

Sorting algorithm visualizerWatch 7 sorting algorithms (bubble, selection, insertion, shell, merge, quick and heap) step by step as bar charts, and compare their comparison and write countsDijkstra's algorithm calculatorCompute shortest paths and distances from a list of weighted edges, and follow each step of finalizing vertices in a table and a diagram

Books on Data Structures and Algorithms Ad

As an Amazon Associate I earn from qualifying purchases.

More Data Structures and Algorithms questions

  1. The (name, score) records (A, 80), (B, 70), (C, 80), (D, 70) are in this order. If they are sorted by score in ascending order with a stable sort, in what order do the names appear?
  2. Which is a typical case in which quicksort takes O(n²) time?
  3. In merge sort, the two sorted runs 1, 4, 7, 9 and 2, 3, 8, 10 are merged into one by repeatedly comparing their front elements and outputting the smaller. When one run is empty, the rest of the other is output without comparisons. How many comparisons are made?
  4. A binary heap is stored in an array a[0], a[1], a[2], … with the root at a[0], filling each level from left to right starting at the top. Which are the children and the parent of a[4]?
  5. A max-heap, in which each parent's value is at least as large as its children's, is stored in an array with the root at a[0]. 45 is added to the heap 50, 30, 40, 10, 20, 35 by placing it at the end and then swapping it with its parent as long as it is larger than the parent. What is the resulting array?