Unexpected Time Complexity in Merge Sort Implementation with Linked Lists in Python
I've searched everywhere and can't find a clear answer. After trying multiple solutions online, I still can't figure this out. I'm currently trying to implement a merge sort algorithm for a singly linked list in Python, and I'm noticing some unexpected behavior with the time complexity. I expected it to be O(n log n) due to the divide-and-conquer approach, but my performance tests suggest it's closer to O(n^2) for larger lists. Here's a simplified version of my code: ```python class ListNode: def __init__(self, value=0, next=None): self.value = value self.next = next class MergeSort: def merge_sort(self, head): if not head or not head.next: return head mid = self.get_middle(head) right = mid.next mid.next = None # Split the list into two halves left_sorted = self.merge_sort(head) right_sorted = self.merge_sort(right) return self.merge(left_sorted, right_sorted) def get_middle(self, head): slow = head fast = head while fast and fast.next: slow = slow.next fast = fast.next.next return slow def merge(self, left, right): if not left: return right if not right: return left if left.value < right.value: left.next = self.merge(left.next, right) return left else: right.next = self.merge(left, right.next) return right ``` I tested it with a linked list of 10,000 elements, and the execution time significantly increased as I added more nodes, leading me to suspect that the merging process is not as efficient as it should be. I'm particularly concerned about the recursive nature of the merge function and whether it's causing too many unnecessary comparisons or iterations. I also ensured I'm not inadvertently creating new nodes during the merge, which could lead to a time complexity blow-up. Could this recursive merge be the culprit, or am I missing something regarding how the linked list operations impact the overall complexity? Any insights would be greatly appreciated! I'd really appreciate any guidance on this. For context: I'm using Python on macOS. Is there a better approach? Any feedback is welcome!