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.