Implementing the Merge Sort Algorithm

Sorting is a fundamental operation in computer science, crucial for efficient data retrieval and organization. This challenge asks you to implement the Merge Sort algorithm, a powerful and efficient sorting algorithm based on the divide-and-conquer paradigm. Mastering Merge Sort demonstrates a strong understanding of recursion and algorithmic efficiency.

Problem Description

You are tasked with implementing the Merge Sort algorithm in Python. Merge Sort works by recursively dividing an unsorted list into smaller sublists until each sublist contains only one element (which is inherently sorted). Then, it repeatedly merges the sublists to produce new sorted sublists until there is only one sorted list remaining.

Your function should take an unsorted list of numbers as input and return a new sorted list containing the same numbers. The algorithm should be implemented recursively. You must implement both the merge_sort function (the main function) and the merge function (which merges two sorted sublists).

Key Requirements:

• Recursive Implementation: The merge_sort function must be implemented recursively.
• merge Function: You must implement a helper function called merge that takes two sorted lists as input and returns a new sorted list containing all elements from both input lists.
• Stability: While not strictly required, strive for a stable sort. A stable sort maintains the relative order of equal elements in the original list.
• No Built-in Sort Functions: You are not allowed to use Python's built-in sort() method or the sorted() function. The goal is to implement the algorithm yourself.

Expected Behavior:

The function should correctly sort lists of numbers, including lists with duplicate values and empty lists.

Edge Cases to Consider:

• Empty list: Should return an empty list.
• List with one element: Should return the same list.
• List with duplicate elements: Should maintain the relative order of equal elements (stability).
• Lists with negative numbers.

Examples

Example 1:

Input: [38, 27, 43, 3, 9, 82, 10]
Output: [3, 9, 10, 27, 38, 43, 82]
Explanation: The input list is recursively divided into smaller sublists until each sublist contains one element. Then, the sublists are merged back together in sorted order.

Example 2:

Input: [12, 11, 13, 5, 6, 7]
Output: [5, 6, 7, 11, 12, 13]
Explanation:  Similar to Example 1, the list is recursively divided and merged to produce a sorted list.

Example 3:

Input: []
Output: []
Explanation: An empty list remains an empty list after sorting.

Example 4:

Input: [5, 2, 8, 1, 9, 4, 7, 3, 6]
Output: [1, 2, 3, 4, 5, 6, 7, 8, 9]
Explanation: A more complex example demonstrating the algorithm's ability to handle various input orders.

Constraints

• Input List Size: The input list can contain up to 1000 elements.
• Element Type: The list will contain only integers.
• Performance: While not strictly enforced, aim for an average time complexity of O(n log n), which is characteristic of Merge Sort. Avoid solutions with O(n^2) or worse complexity.
• Memory Usage: The algorithm should create new lists during the merging process. Excessive memory usage is discouraged, but not penalized heavily.

Notes

• The merge function is the core of the algorithm. Ensure it correctly merges two sorted lists into a single sorted list.
• Consider how to handle the base case of the recursion (when a sublist contains only one element).
• Think about how to divide the list into sublists efficiently.
• Debugging recursive functions can be challenging. Use print statements or a debugger to trace the execution of your code.
• Focus on clarity and readability in your code. Well-commented code is always appreciated.