implement a merge sort using python only pure python
- User
implement a merge sort using python only pure python
Assistant
Merge Sort Implementation in Pure Python
Here's a complete implementation of the merge sort algorithm using only pure Python (no external libraries):
def merge_sort(arr): """ Sorts an array in ascending order using the merge sort algorithm. Args: arr: List of elements to be sorted Returns: A new sorted list containing all elements from the input list """ # Base case: if the array has 1 or 0 elements, it's already sorted if len(arr) <= 1: return arr.copy() # Return a copy to maintain immutability # Split the array into two halves mid = len(arr) // 2 left_half = arr[:mid] right_half = arr[mid:] # Recursively sort both halves left_sorted = merge_sort(left_half) right_sorted = merge_sort(right_half) # Merge the sorted halves return merge(left_sorted, right_sorted) def merge(left, right): """ Merges two sorted lists into one sorted list. Args: left: First sorted list right: Second sorted list Returns: A new sorted list containing all elements from both input lists """ result = [] left_index = right_index = 0 # Traverse both lists and compare elements while left_index < len(left) and right_index < len(right): if left[left_index] < right[right_index]: result.append(left[left_index]) left_index += 1 else: result.append(right[right_index]) right_index += 1 # Append any remaining elements from left list while left_index < len(left): result.append(left[left_index]) left_index += 1 # Append any remaining elements from right list while right_index < len(right): result.append(right[right_index]) right_index += 1 return result # Example usage if __name__ == "__main__": unsorted_list = [38, 27, 43, 3, 9, 82, 10] print("Unsorted list:", unsorted_list) sorted_list = merge_sort(unsorted_list) print("Sorted list:", sorted_list)Key Features:
- Pure Python: Uses only built-in Python features with no external dependencies
- Recursive Implementation: The algorithm recursively divides the array until it reaches base cases
- Stable Sort: Maintains the relative order of equal elements
- Time Complexity: O(n log n) in all cases
- Space Complexity: O(n) due to the auxiliary space used during merging
How It Works:
- The
merge_sortfunction divides the input array into two halves - It recursively sorts each half
- The
mergefunction combines the two sorted halves into a single sorted array - The process continues until the entire array is sorted
You can test it with any list of comparable elements (numbers, strings, etc.). The example shows sorting a list of integers.
Other models, same or similar prompt
Responses were produced in different, uncontrolled contexts (system prompts, settings, prior turns). This is not a benchmark.