---
id: 587d825c367417b2b2512c8f
title: Реалізуйте сортування злиттям
challengeType: 1
forumTopicId: 301614
dashedName: implement-merge-sort
---

# --description--

Ще один поширений алгоритм проміжного сортування — сортування злиттям. Як і швидке сортування, сортування злиттям також використовує принцип «Розділяй та володарюй», рекурсивну методологію для сортування масиву. Його перевага в тому, що два масиви порівняно легко відсортувати, якщо кожен з них вже відсортовано. Але ми почнемо тільки з одного масиву як з вхідного, то як же отримати з нього два відсортованих масиви? Ми можемо рекурсивно поділити початковий ввід на два, доки не досягнемо базового випадку масиву з одним елементом. Одноелементний масив вже відсортований, тому ми можемо почати комбінувати. Ця комбінація розгорне рекурсивні виклики, які розбивають початковий масив, врешті створюючи кінцевий відсортований масив з усіх елементів. Кроки сортування злиттям:

**1)** Рекурсивно розділити вхідний масив навпіл, поки підмасив лише з одним елементом не буде сформовано.

**2)** Об’єднати кожен відсортований підмасив разом, щоб створити кінцевий відсортований масив.

Сортування злиттям є ефективним методом сортування із часовою складністю *O(nlog(n))*. Цей алгоритм популярний, оскільки він є продуктивним та відносно простим для реалізації.

До речі, це буде останній алгоритм сортування, який ми висвітлюємо тут. Однак пізніше в розділі про деревовидні структури даних ми опишемо пірамідальне сортування — ще один ефективний метод сортування, який вимагає двійкової купи у своїй реалізації.

**Інструкція:** напишіть функцію `mergeSort`, яка приймає масив цілих чисел як ввід та повертає масив цих цілих чисел у відсортованому порядку (від найменшого до найбільшого). Хороший спосіб реалізувати це — написати одну функцію (наприклад, `merge`), яка відповідає за злиття двох відсортованих масивів, та ще одну функцію (наприклад, `mergeSort`), яка відповідає за рекурсію, що виробляє одноелементні масиви. Успіхів!

# --hints--

`mergeSort` має бути функцією.

```js
assert(typeof mergeSort == 'function');
```

`mergeSort` має повернути впорядкований масив (від найменшого до найбільшого).

```js
assert(
  isSorted(
    mergeSort([
      1,
      4,
      2,
      8,
      345,
      123,
      43,
      32,
      5643,
      63,
      123,
      43,
      2,
      55,
      1,
      234,
      92
    ])
  )
);
```

`mergeSort([1,4,2,8,345,123,43,32,5643,63,123,43,2,55,1,234,92])` має повернути масив без змін, окрім послідовності.

```js
assert.sameMembers(
  mergeSort([
    1,
    4,
    2,
    8,
    345,
    123,
    43,
    32,
    5643,
    63,
    123,
    43,
    2,
    55,
    1,
    234,
    92
  ]),
  [1, 4, 2, 8, 345, 123, 43, 32, 5643, 63, 123, 43, 2, 55, 1, 234, 92]
);
```

`mergeSort` не має використовувати вбудований метод `.sort()`.

```js
assert(isBuiltInSortUsed());
```

# --seed--

## --after-user-code--

```js
function isSorted(a){
  for(let i = 0; i < a.length - 1; i++)
    if(a[i] > a[i + 1])
      return false;
  return true;
}

function isBuiltInSortUsed(){
  let sortUsed = false;
  Array.prototype.sort = () => sortUsed = true;
  mergeSort([0, 1]);
  return !sortUsed;
}
```

## --seed-contents--

```js
function mergeSort(array) {
  // Only change code below this line
  return array;
  // Only change code above this line
}
```

# --solutions--

```js
function mergeSort(array) {
  if (array.length === 1) {
    return array;
  } else {
    const splitIndex = Math.floor(array.length / 2);
    return merge(
      mergeSort(array.slice(0, splitIndex)),
      mergeSort(array.slice(splitIndex))
    );
  }

  // Merge two sorted arrays
  function merge(array1, array2) {
    let merged = [];
    while (array1.length && array2.length) {
      if (array1[0] < array2[0]) {
        merged.push(array1.shift());
      } else if (array1[0] > array2[0]) {
        merged.push(array2.shift());
      } else {
        merged.push(array1.shift(), array2.shift());
      }
    }

    // After looping ends, one array is empty, and other array contains only
    // values greater than all values in `merged`
    return [...merged, ...array1, ...array2];
  }
}

mergeSort([1, 4, 2, 8, 345, 123, 43, 32, 5643, 63, 123, 43, 2, 55, 1, 234, 92]);
```
