👀 Views: 99 💬 Answers: 1 📅 Created: 2025-06-06

algorithms sorting merge-sort Python

This might be a silly question, but I'm updating my dependencies and I'm relatively new to this, so bear with me. I'm implementing the Merge Sort algorithm in Python, but I'm working with issues when sorting large lists. For smaller lists, the algorithm works as expected, but with larger datasets, the output seems to be incorrectly sorted. Here's the implementation I'm currently using: ```python def merge_sort(arr): if len(arr) > 1: mid = len(arr) // 2 left_half = arr[:mid] right_half = arr[mid:] merge_sort(left_half) merge_sort(right_half) i = j = k = 0 while i < len(left_half) and j < len(right_half): if left_half[i] < right_half[j]: arr[k] = left_half[i] i += 1 else: arr[k] = right_half[j] j += 1 k += 1 while i < len(left_half): arr[k] = left_half[i] i += 1 k += 1 while j < len(right_half): arr[k] = right_half[j] j += 1 k += 1 return arr ``` I tested this function with the following code: ```python random_list = [3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5] print(merge_sort(random_list)) ``` This works fine, but when I run it with a larger dataset, say a list of 10,000 random integers, the output is not sorted correctly. For example: ```python import random large_list = random.sample(range(10000), 10000) print(merge_sort(large_list)) ``` I get outputs that have elements out of order, such as `large_list[0]` could be greater than `large_list[1]`. I've double-checked the merge logic and I don't see any issues, but I suspect it might be related to how the merge process is handling the indices. Could anyone point out what might be going wrong or suggest improvements? I'm using Python 3.10 and have not encountered this scenario previously with smaller lists. Any help would be greatly appreciated! Any help would be greatly appreciated! The stack includes Python and several other technologies. Is there a better approach? This is my first time working with Python latest. Any pointers in the right direction? Cheers for any assistance!