Data Structures and Algorithms Flashcards

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

Answer: Merge Sort

Merge Sort guarantees O(n log n) in all cases by repeatedly dividing and merging subarrays.

What is the best-case time complexity of Bubble Sort?

Answer: O(n)

With an already-sorted array, Bubble Sort with an early-exit flag runs in O(n) — one pass with no swaps.

Quick Sort selects a 'pivot' element and then:

Answer: Partitions elements into those less than and greater than the pivot

Quick Sort partitions the array around the pivot so all smaller elements are on the left and larger ones on the right.

Which of the following sorting algorithms is NOT comparison-based?

Answer: Radix Sort

Radix Sort distributes elements into buckets by digit value, bypassing direct element comparisons.

Insertion Sort is most efficient when the input data is:

Answer: Nearly sorted

Nearly sorted input minimizes the number of shifts required, making Insertion Sort approach O(n) performance.

What additional data structure does Heap Sort use to achieve O(n log n) complexity?

Answer: Binary Heap

Heap Sort builds a binary heap from the input and repeatedly extracts the maximum to produce a sorted array.

Which sorting algorithm is stable by default, preserving the relative order of equal elements?

Answer: Merge Sort

Merge Sort is stable because it always picks left-side elements first when two values are equal during merging.