22. Merge Sort: Implementation and Merging Step (Part 2)

The core of Merge Sort's efficiency lies in the merge function, which takes two sorted sublists and combines them into one sorted list in O(N) time.

The Merge Function

Imagine combining two decks of cards, both already sorted. You only need to look at the top card of each deck and pick the smaller one to add to the final deck.

1. Use two pointers, one for the start of the left sublist (L) and one for the start of the right sublist (R).
2. While both sublists have elements, compare the elements pointed to.
3. Copy the smaller element into the final array and advance its pointer.
4. Once one sublist is exhausted, copy all remaining elements from the other sublist.

Efficiency Analysis

• Time Complexity: O(N log N) for worst, average, and best cases.
  • log N comes from the 'divide' phase (how many times we split the list in half).
  • N comes from the 'merge' phase (we look at every element once during each merge level).
• Space Complexity: O(N) auxiliary space, as it requires a temporary array to perform the merging.