CODEWITHSUNDEEP
time-complexitymergesort
Victor
Victor

Reputation: 17107

What sorting technique does merge sort use while merging

At the last but one step of the merge sort where we have two sorted lists and we are trying to combine them into one sorted list, how would the logic go?

This is what my naive mind came up with: Take each element of list #1 and compare it with each element of list#2 and find its place in list #2. BAsically like an insertion sort.

But obviously this is not how it happens because this gives me a complexity of O(n^2). But merge sort is O(nlogn). So how does the final step happens?

Upvotes: 1

Views: 147

Answers (2)

Jerry Coffin
Jerry Coffin

Reputation: 490408

It depends heavily on how you've structured the data you're sorting.

Merge sort tends to be used primarily for external sorting, such as sorting files on disk. In this case, you normally take inputs from some number of input files, and write the results to a separate output file.

If you're sorting linked lists, you generally do about the same -- take N input lists and produce one output list. Since you can move elements from one list to another just by manipulating the links, this doesn't require (much) extra storage or time.

You really seem to be asking about sorting an array in place. If you want to merge-sort an array in-place, there are a couple of algorithms known, but they're somewhat non-trivial.

[I don't like using only links to what I'd guess is the real answer here, but the algorithms really are a bit much to try to even outline here.]

Upvotes: 0

Dark Falcon
Dark Falcon

Reputation: 44191

It uses merge sort. Merge sort doesn't have a separate sorting algorithm, it IS a sorting algorithm.

So your original lists are already sorted, so the smallest element is always at the beginning. Compare A and B. Take the lesser of the two and add it to the end of the result list. Repeat until both source lists are empty.

Upvotes: 1

Related Questions