FAQ: Merge Sort: Conceptual - How To Merge Sort:

[wiki-bot]

This community-built FAQ covers the “How To Merge Sort:” exercise from the lesson “Merge Sort: Conceptual”.

Paths and Courses
This exercise can be found in the following Codecademy content:

Sorting Algorithms

FAQs on the exercise How To Merge Sort:

There are currently no frequently asked questions associated with this exercise – that’s where you come in! You can contribute to this section by offering your own questions, answers, or clarifications on this exercise. Ask or answer a question by clicking reply () below.

If you’ve had an “aha” moment about the concepts, formatting, syntax, or anything else with this exercise, consider sharing those insights! Teaching others and answering their questions is one of the best ways to learn and stay sharp.

Join the Discussion. Help a fellow learner on their journey.

Ask or answer a question about this exercise by clicking reply () below!

Agree with a comment or answer? Like () to up-vote the contribution!

Need broader help or resources? Head here.

Looking for motivation to keep learning? Join our wider discussions.

Learn more about how to use this guide.

Found a bug? Report it!

Have a question about your account or billing? Reach out to our customer support team!

None of the above? Find out where to ask other questions here!

[spacetyrant]

The question in the “instruction” part of this lesson is:

How can we be sure that the leftover contents from two lists that we’re merging are all larger than the result we’ve built so far?

I’m not sure I understand it, however – why would there be leftover content when merging in the first place? Isn’t the point of the merge to reassemble all of the broken-down elements back together again into a single list?

[ngwolfhare]

Literally what I was just thinking… I watch someone solve a two sorted linked list problem and… It seems like that’s just rewiring everything with no waste…never once was there a concern of making new stuff or having left overs. That kind of defeats the purpose of merge sort wouldn’t it ?? Literally you break it down to the base case and then recursively build up from there!!! Am I missing something???

[ngwolfhare]

With a bit of a goog:

"Merge sort is an algorithm whose complexity is O(nlog(n)) is better than insertion sort, selection sort and bubble sort. It’s important because for an input “n” large enough it will grow slower than other algorithms.

But everything has a price. Merge sort doesn’t work in place, it means that it has to make complete copies of the entire subarray in each recursive call.

In other hand insertion sort just require an only one array entry rather than copies of all array entries.

As well, merge sort algorithm it’s a great start point to employ divide and conquer paradigm."

maybe that’s where the left over concern is coming from

[jameskeezer]

I was also confused by this question, but I think I figured it out.

What is the “leftover contents from the two lists” ?

Consider this example: We are currently merging two sorted sublists that each contain three elements:

[ 2, 3, 4 ] and [ 1, 5, 6 ]

Each step would add the smaller of the first element in each list to a new sublist:

Compare first element from each list: 2 > 1 - newSublist = [ 1 ]

Old sublists: [ 2, 3, 4 ] and [ 5, 6 ]

Compare: 2 < 5 - newSublist [ 1, 2 ]

Old sublists: [ 3, 4 ] and [ 5, 6 ]

Compare: 3 < 5 - newSublist [ 1, 2, 3 ]

Old sublists: [ 4 ] and [ 5, 6 ]

Compare: 4 < 5 - newSublist [ 1, 2, 3, 4 ]

Old sublists: [ ] and [ 5, 6 ]

The non-empty old sublist is the “leftover contents” - [ 5, 6 ]

The question asks: how can we be sure that the leftover contents from the two lists are all larger than the result we’ve built so far?

The leftover contents - [ 5, 6 ] - are all larger than the result we’ve built so far - [ 1, 2, 3, 4 ] - because all of the elements in the new list have been compared to the smallest element of the old array that still contains elements.