Skip to content
TheChatArchiveThe Chat Archive
Mistralmistral-medium-2505· Mistral AIHugging Face LMArena Human Preference 140K

implement a merge sort using python only pure python

From a Chatbot Arena battleThe same person sent this prompt to two anonymous models at once. Compare it with Claudeclaude-3-5-haiku-20241022’s answer.
  1. User

    implement a merge sort using python only pure python

  2. Mistral 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:

    1. Pure Python: Uses only built-in Python features with no external dependencies
    2. Recursive Implementation: The algorithm recursively divides the array until it reaches base cases
    3. Stable Sort: Maintains the relative order of equal elements
    4. Time Complexity: O(n log n) in all cases
    5. Space Complexity: O(n) due to the auxiliary space used during merging

    How It Works:

    1. The merge_sort function divides the input array into two halves
    2. It recursively sorts each half
    3. The merge function combines the two sorted halves into a single sorted array
    4. 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.

Responses were produced in different, uncontrolled contexts (system prompts, settings, prior turns). This is not a benchmark.