напиши алгоритм merge sort на python
- User
напиши алгоритм merge sort на python
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)Объяснение
- Функция
merge_sortпринимает список элементов в качестве входных данных и возвращает отсортированный список. - Если список содержит один или ноль элементов, он уже отсортирован, поэтому функция возвращает список как есть.
- Список делится на две части:
left_halfиright_half. - Обе части рекурсивно сортируются с помощью функции
merge_sort. - Отсортированные части объединяются с помощью функции
merge. - Функция
mergeсравнивает элементы из обоих списков и добавляет меньший элемент в объединенный список. - Оставшиеся элементы из обоих списков добавляются в объединенный список, если они есть.
Время работы
- Лучший случай: O(n log n)
- Средний случай: O(n log n)
- Худший случай: O(n log n)
Пространственная сложность
- O(n) для вспомогательного массива, используемого при объединении.
- Функция
Other models, same or similar prompt
Responses were produced in different, uncontrolled contexts (system prompts, settings, prior turns). This is not a benchmark.