Skip to content
TheChatArchiveThe Chat Archive
Metallama-4-maverick-17b-128e-instruct· MetaHugging Face LMArena Human Preference 140K

напиши алгоритм merge sort на python

From a Chatbot Arena battleThe same person sent this prompt to two anonymous models at once. Compare it with gpt-4o-2024-11-20’s answer.
  1. User

    напиши алгоритм merge sort на python

  2. Meta Assistant

    Merge Sort на Python

    Merge sort - это алгоритм сортировки, который использует подход "разделяй и властвуй" для сортировки списков элементов. Он работает путем разделения списка на более мелкие части, сортировки их индивидуально и последующего объединения отсортированных частей в единый отсортированный список.

    Код

    def merge_sort(arr):
        """
        Сортировка списка с помощью алгоритма merge sort.
    
        :param arr: Список элементов для сортировки.
        :return: Отсортированный список.
        """
        # Если список содержит один или ноль элементов, он уже отсортирован.
        if len(arr) <= 1:
            return arr
    
        # Разделите список на две части.
        mid = len(arr) // 2
        left_half = arr[:mid]
        right_half = arr[mid:]
    
        # Рекурсивно отсортируйте обе части.
        left_half = merge_sort(left_half)
        right_half = merge_sort(right_half)
    
        # Объедините отсортированные части.
        return merge(left_half, right_half)
    
    
    def merge(left, right):
        """
        Объедините два отсортированных списка в один отсортированный список.
    
        :param left: Первый отсортированный список.
        :param right: Второй отсортированный список.
        :return: Объединенный отсортированный список.
        """
        merged = []
        left_index = 0
        right_index = 0
    
        # Сравните элементы из обоих списков и добавьте меньший в объединенный список.
        while left_index < len(left) and right_index < len(right):
            if left[left_index] <= right[right_index]:
                merged.append(left[left_index])
                left_index += 1
            else:
                merged.append(right[right_index])
                right_index += 1
    
        # Добавьте оставшиеся элементы из обоих списков, если они есть.
        merged.extend(left[left_index:])
        merged.extend(right[right_index:])
    
        return merged
    
    
    # Пример использования
    if __name__ == "__main__":
        arr = [64, 34, 25, 12, 22, 11, 90]
        sorted_arr = merge_sort(arr)
        print("Отсортированный список:", sorted_arr)
    

    Объяснение

    1. Функция merge_sort принимает список элементов в качестве входных данных и возвращает отсортированный список.
    2. Если список содержит один или ноль элементов, он уже отсортирован, поэтому функция возвращает список как есть.
    3. Список делится на две части: left_half и right_half.
    4. Обе части рекурсивно сортируются с помощью функции merge_sort.
    5. Отсортированные части объединяются с помощью функции merge.
    6. Функция merge сравнивает элементы из обоих списков и добавляет меньший элемент в объединенный список.
    7. Оставшиеся элементы из обоих списков добавляются в объединенный список, если они есть.

    Время работы

    • Лучший случай: O(n log n)
    • Средний случай: O(n log n)
    • Худший случай: O(n log n)

    Пространственная сложность

    • O(n) для вспомогательного массива, используемого при объединении.

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