sort.merge #3
Description
Implement Merge Sort Algorithm
Description
Implement the merge() method in the Sorter class (sort.py). This method should use the merge sort algorithm to sort a list of elements based on a custom comparator function.
Requirements
Method Signature:
@staticmethod
def merge(data: List[Any], comparator: Callable[[Any, Any], bool]) -> List[Any]Parameters:
data: A list of elements to sortcomparator: A function that takes two elements and returnsTrueif the first should come before the second
Returns:
- A new sorted list (do not modify the original list)
Algorithm Details
Merge sort is a divide-and-conquer algorithm that:
- Divides the list into two halves
- Recursively sorts each half
- Merges the two sorted halves back together
Time Complexity: O(n log n) in all cases
Space Complexity: O(n)
Performance Requirements
Your implementation must pass the performance test with the following criteria:
- Dataset size: 10,000 random integers
- Maximum time: 1 second
- The algorithm should efficiently handle large datasets
Implementation Guidelines
- Use recursion to divide the list
- Implement a merge helper function to combine sorted sublists
- Do not modify the original list - work on a copy
- Handle edge cases:
- Empty lists
- Single-element lists
- Already sorted lists
- Lists with duplicate elements
- Lists with negative numbers
Testing
Run the test suite to verify your implementation:
python3 -m colorful_test test_sort.pyAll tests related to merge() must pass, including:
- Basic sorting (ascending/descending)
- Edge cases (empty, single element, duplicates)
- Immutability (original list unchanged)
- Performance test
- Consistency with other sorting methods
Example Usage
from sort import Sorter
data = [5, 2, 8, 1, 9]
sorted_asc = Sorter.merge(data, lambda a, b: a < b)
print(sorted_asc) # [1, 2, 5, 8, 9]
sorted_desc = Sorter.merge(data, lambda a, b: a > b)
print(sorted_desc) # [9, 8, 5, 2, 1]Acceptance Criteria
- Method correctly sorts lists using merge sort algorithm
- All edge cases are handled
- Original list is not modified
- All tests pass (24+ tests)
- Performance test completes within 1 second for 10,000 elements
- Code is clean and well-commented
Resources
Note: Do not modify the test files. Ensure your implementation passes all existing tests.