CODEWITHSUNDEEP
sorting
Sanya
Sanya

Reputation: 159

Sorting technique - most efficient

What sorting technique would you use to sort 10,000 items using just 1000 available slots in your RAM?

  1. Heap Sort
  2. Quick Sort
  3. Bubble Sort
  4. Merge Sort

I am confused between quick and merge sort. Both have average time complexity of nlogn but again heap sort also has the same complexity. Any inputs would be appreciated!

Upvotes: 1

Views: 440

Answers (2)

EJoshuaS - Stand with Ukraine
EJoshuaS - Stand with Ukraine

Reputation: 12191

Time complexity won't help you here - what the question is looking for is space complexity. Just as a hint, n = 10000 and you have only 1000 available spaces, so you need to pick an algorithm that is better than O(n) space complexity even in the worst case.

Upvotes: 2

Richard
Richard

Reputation: 61489

This seems like an HW question, so I'd prefer not to answer directly. In general, though, since your RAM is small and your list is big, you'll do best with something like a cache oblivious algorithm.

Upvotes: 2

Related Questions