4
$\begingroup$

I don't quite understand why in-place sort merge sort isn't preferred over not-in place? Is it because theoretically in place merge sort is better because of its memory complexity tradeoff, but in industry other factors out -weight the memory tradeoff? Likewise, with quicksort the opposite is true ie, in place is preferred over not in place, which intuitively makes sense.

$\endgroup$
  • 2
    $\begingroup$ See here for a discussion on tradeoffs for in-place merge sort. $\endgroup$ – ryan Apr 12 at 20:53
  • $\begingroup$ "why in-place sort merge sort isn't preferred" Could you perhaps explain in what context this is not preferred? For example, in the classroom, I would prefer the not in place variant, as it is much simpler to describe. $\endgroup$ – Discrete lizard Apr 13 at 9:16
  • $\begingroup$ See here. Swapping stuff around places far apart is much slower -in practice- than just copying it in order (because of the caching architecture). It also happens that copying in order is a highly optimized operation because its used too often. In industry, you generally don't care as you just call whatever sorting function is provided by default. If you do care, you're likely doing high performance work, and you usually have other factors to take into consideration $\endgroup$ – Misguided Apr 16 at 21:26
0
$\begingroup$

Merge sort on arrays cannot be performed in-place.

$\endgroup$
  • 6
    $\begingroup$ This does not answer the question, merge sort can be performed in place. See here. $\endgroup$ – ryan Apr 12 at 20:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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