time complexity - What sorting technique does merge sort use while merging -


at last 1 step of merge sort have 2 sorted lists , trying combine them 1 sorted list, how logic go?

this naive mind came with: take each element of list #1 , compare each element of list#2 , find place in list #2. insertion sort.

but not how happens because gives me complexity of o(n^2). merge sort o(nlogn). how final step happens?

it uses merge sort. merge sort doesn't have separate sorting algorithm, sorting algorithm.

so original lists sorted, smallest element @ beginning. compare , b. take lesser of 2 , add end of result list. repeat until both source lists empty.


Comments

Popular posts from this blog

Line ending issue with Mercurial or Visual Studio -

python - Received unregistered task using Celery with Django -

c# - Delving into the world of XML (Windows Phone) Error I dont understand (The ' ' character, hexadecimal value 0x20, cannot be included in a name.) -