I have the following homework question: You develop a video surveillance software that must run on real-time data. In one of the steps of the algorithm executed with each image captured by the camera, you have to sort some numbers. Considering that the average execution time of QuickSort is better than that of MergeSort, which Sorting should you consider using? justify

I know that QuickSort isn't good with larger dataset as opposed to MergeSort. I also think that because we are working with data that continuously updates speed is incredibly important. But considering that its real-time that means that the size of the data set is small initialy and then grows.

It seems like a trap to go for QuickSort because the question is heavily promoting it. On the other hand MergeSort is more stable it always have a complexity of O(n log n). I don't know which to choose and how to justify it properly.

closed as too broad by Robert Harvey Apr 7 at 20:37

Please edit the question to limit it to a specific problem with enough detail to identify an adequate answer. Avoid asking multiple distinct questions at once. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.

  • I'd use the Bad Question Sort. There are at least a half-dozen variables that would favor one or the other. The question only mentions one and not even explicitly as a requirement. If your prof is trying to teach you how to reason about how you develop your software, he's doing a terrible job of it. – Blrfl Apr 6 at 23:20
  • 3
    @Blrfl Strange thing to say, when the Prof is obviously trying to get the student to think about the properties of both and in what conditions either is better - and what conditions might apply here. In particular I presume the lesson is that average faster isn't always what you aim for, as that is the default many students would rank such algorithms by. – Frank Hopkins Apr 6 at 23:31
  • Relevant:pdfs.semanticscholar.org/0f8f/… – NoChance Apr 7 at 9:23
  • 1
    @FrankHopkins The question invites a comparison between the sorts, but that comparison raises more questions than it answers. OP was forced to make some assumptions in the second paragraph that could turn out to be wrong (e.g., maybe the set of numbers isn't growing and is instead some figure calculated from the last five frames), invalidating the justification. The only valid answers to the question as written would be "consider both until the other properties of the data are known" and "if average speed is the only criterion, the question answers itself." – Blrfl Apr 7 at 11:17
  • @Blrfl No, a valid answer is one that considers possible constraints and then either assumes some given the setting that justify a choice or talks the major set of combinations through. The point in education exercises often isn't to solve one particular concrete setup but to think about the possible setups you could face and how you then apply your tools. And likely, the realisation that those assumptions are just that and may need to be verified is likely part of the exercise, i.e. if you make assumptions what you aim for you should be able to root them in the setting. – Frank Hopkins Apr 7 at 15:41

Likely there isn't necessarily a single correct answer, but your professor wants to see how well you know the properties of both algorithms and whether you can justify a set of constraints / goals in the given setting that make you prefer one (for good reasons).

That said, the hint that it's real-time processing strongly suggests one line of reasoning that you already seem to have come up with half-way.


The point here is that average performance is not relevant in this case. You want an algorithm that, in a worst case scenario, will still fit in the time slot you have been granted. That time slot is one frame period. When you are done processing you have to wait for the next frame anyway. Then it is better to need 90% of the slot in a worst case scenario that occurs often then to do it in 25% of the slot for 99% of the cases but to fall short in the remaining 1%.

Not the answer you're looking for? Browse other questions tagged or ask your own question.