Advertisement
vit134

Сортировка слиянием

Nov 15th, 2018
136
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. /*
  2.     Сортировка слиянием
  3. */
  4.  
  5. const merge = (arrFirst, arrSecond) => {
  6.     //console.log(23)
  7.     const arrSort = [];
  8.     let i = j = 0;
  9.     // сравниваем два массива, поочередно сдвигая указатели
  10.     while (i < arrFirst.length && j < arrSecond.length) {
  11.         let arr;
  12.        
  13.         if (arrFirst[i] < arrSecond[j]) {
  14.             arr = arrFirst[i++]
  15.         } else {
  16.             arr = arrSecond[j++]
  17.         }
  18.        
  19.         arrSort.push(arr);
  20.     }
  21.     // обрабатываем последний элемент при разной длине массивов
  22.     // и возвращаем один отсортированный массив
  23.     return [
  24.         ...arrSort,
  25.         ...arrFirst.slice(i),
  26.         ...arrSecond.slice(j)
  27.     ];
  28. };
  29.  
  30. const mergeSort = arr => {
  31.     // Проверяем корректность переданных данных
  32.     if (!arr || !arr.length) {
  33.         return null;
  34.     }
  35.     //Если массив содержит один элемент просто возвращаем его
  36.     if (arr.length <= 1) {
  37.         return arr;
  38.     }
  39.     // Находим середину массива и делим его на два
  40.     const middle = Math.floor(arr.length / 2);
  41.     const arrLeft = arr.slice(0, middle);
  42.     const arrRight = arr.slice(middle);
  43.     // Для новых массивов снова вызываем сортировку,
  44.     // сливаем их и возвращаем снова единый массив
  45.    
  46.     return merge(mergeSort(arrLeft), mergeSort(arrRight));;
  47. };
  48.  
  49.  
  50. console.log(mergeSort([-4, 1, Infinity, 3, 3, 0]))
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement