<commit_before>---
id: 587d825c367417b2b2512c8f
title: Implement Merge Sort
challengeType: 1
videoUrl: ''
localeTitle: Реализация Merge Sort
---

## Description
<section id="description"> Другим промежуточным алгоритмом сортировки, который очень распространен, является сортировка слияния. Подобно быстрой сортировке, сортировка слияния также использует метод рекурсивного рекурсивного анализа для разделения массива. Он использует тот факт, что относительно легко сортировать два массива, пока они сортируются в первую очередь. Но мы начнем с только одного массива в качестве входных данных, так как мы можем перейти к двум отсортированным массивам? Ну, мы можем рекурсивно разделить исходный ввод на два, пока не достигнем базового случая массива с одним элементом. Массив из одного элемента естественно сортируется, поэтому мы можем начать комбинировать. Эта комбинация будет раскручивать рекурсивные вызовы, разделяющие исходный массив, в конечном итоге создавая окончательный отсортированный массив всех элементов. Затем выполняются шаги сортировки слияния: <strong>1)</strong> рекурсивно разделить входной массив пополам, пока не будет создан суб-массив с только одним элементом. <strong>2)</strong> Объедините каждый отсортированный подматрица вместе, чтобы получить окончательный отсортированный массив. Сортировка Merge - это эффективный метод сортировки со сложностью времени <i>O (nlog (n))</i> . Этот алгоритм популярен, потому что он прост и относительно прост в реализации. В стороне это будет последний алгоритм сортировки, который мы рассмотрим здесь. Однако позже в разделе о структурах древовидных данных мы опишем сортировку кучи, еще один эффективный метод сортировки, который требует бинарной кучи в ее реализации. <strong>Инструкции:</strong> Напишите функцию <code>mergeSort</code> которая принимает массив целых чисел в качестве входных данных и возвращает массив этих целых чисел в отсортированном порядке от наименьшего к наибольшему. Хороший способ реализовать это - написать одну функцию, например <code>merge</code> , которая отвечает за объединение двух отсортированных массивов и другую функцию, например, <code>mergeSort</code> , которая отвечает за рекурсию, которая создает массивы с одним элементом для объединения в слияние. Удачи! <strong>Заметка:</strong> <br> Мы вызываем эту функцию из-за кулис; тестовый массив, который мы используем, закомментирован в редакторе. Попробуйте logging <code>array</code> чтобы увидеть ваш алгоритм сортировки в действии! </section><commit_msg>Changed the description of the algorithm (#25172)<commit_after>---
id: 587d825c367417b2b2512c8f
title: Implement Merge Sort
challengeType: 1
videoUrl: 'https://www.youtube.com/watch?v=TzeBrDU-JaY'
localeTitle: Реализация Merge Sort
---

## Description
<section id="description"> Другим промежуточным алгоритмом сортировки, который очень распространен, является сортировка слияния. Подобно быстрой сортировке, сортировка слиянием также использует метод рекурсивного анализа для разделения массива. Сортировка использует тот факт, что легче сортировать два массива меньшего размера, нежели один большего. В качестве входных данных начнем с неотсортированного массива. Как мы можем перейти к двум отсортированным массивам? Мы можем рекурсивно разделить исходный ввод на два, пока не достигнем базового случая массива с одним элементом. Массив из одного элемента естественно сортируется, поэтому мы можем начать комбинировать. Эта комбинация будет раскручивать рекурсивные вызовы, разделяющие исходный массив, в конечном итоге создавая окончательный отсортированный массив всех элементов. 
  Затем выполняются шаги сортировки слияния: 
  <strong>1)</strong> Рекурсивно разделить входной массив пополам, пока не будет создан массив только с одним элементом.       <strong>2)</strong> Объединтить каждый отсортированный подмассив вместе, чтобы получить окончательный отсортированный массив. 
  Сортировка Merge - это эффективный метод сортировки со алгоритмически-оптимальной сложностью <i>O (nlog (n))</i> . Этот алгоритм популярен, потому что он прост в реализации. Это будет последний эффективный алгоритм сортировки, который мы рассмотрим здесь. Однако позже в разделе о структурах древовидных данных мы опишем сортировку кучи (HeapSort), еще один эффективный метод сортировки, который требует реализацию бинарной кучи. 
  <strong>Инструкции:</strong> Напишите функцию <code>mergeSort</code> которая принимает массив целых чисел в качестве входных данных и возвращает массив этих целых чисел в отсортированном порядке от наименьшего к наибольшему. Хороший способ реализовать это - написать одну функцию, например <code>merge</code> , которая отвечает за объединение двух отсортированных массивов и другую функцию, например, <code>mergeSort</code> , которая отвечает за слияние. Удачи! 
  <strong>Заметка:</strong> <br> Мы вызываем эту функцию из-за кулис; тестовый массив, который мы используем, закомментирован в редакторе. Попробуйте logging <code>array</code> чтобы увидеть ваш алгоритм сортировки в действии! </section>
{'fraction_non_alphanumeric': 0.054011119936457505, 'fraction_numerical': 0.009332803812549643, 'mean_word_length': 6.154829545454546, 'pattern_counts': {'":': 0, '<': 45, '<?xml version=': 0, '>': 45, 'https://': 1, 'lorem ipsum': 0, 'www.': 1, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '1224991', 'n_tokens_mistral': 1999, 'n_tokens_neox': 2358, 'n_words': 589}