Встречается на собеседованиях • сегодня

Расскажи подробнее про любой алгоритм сортировки

Сортировка слиянием (Merge Sort) — это стабильный алгоритм сортировки, работающий по принципу «разделяй и властвуй». Он рекурсивно разбивает массив на две половины, сортирует каждую, а затем сливает их в один отсортированный массив.

Алгоритм:

  1. Разделение: Массив делится пополам, пока не останутся подмассивы из одного элемента.
  2. Слияние: Отсортированные подмассивы объединяются в новый массив в правильном порядке.

Преимущества:

  • Гарантированная сложность O(n log n) даже в худшем случае.
  • Стабильность (сохраняет порядок равных элементов).

Недостатки:

  • Требует дополнительной памяти O(n).

Пример на Python:

python
def merge_sort(arr):
    if len(arr) > 1:
        mid = len(arr) // 2
        left = arr[:mid]
        right = arr[mid:]
        merge_sort(left)
        merge_sort(right)
        
        i = j = k = 0
        while i < len(left) and j < len(right):
            if left[i] < right[j]:
                arr[k] = left[i]
                i += 1
            else:
                arr[k] = right[j]
                j += 1
            k += 1
        
        while i < len(left):
            arr[k] = left[i]
            i += 1
            k += 1
        
        while j < len(right):
            arr[k] = right[j]
            j += 1
            k += 1
Sophi
Софи собрала все вопросы. Тренируйся и получай
офферы быстрее!
Попробовать бесплатноArrow

Следующий вопрос

Это единственный вопрос по вашему фильтру

как отвечать на вопрос
пример собеседования
фреймворки на собеседовании
типичные вопросы junior
интервью вопросы и ответы