merge sort / сортировка слиянием

234

01 февраля 2018, 20:20

Здравствуйте! Пытаюсь реализовать сортировку слиянием. Общий принцип довольно понятен, но в процессе реализации возникли проблемы. Необходимо реализовать так, что бы в процессе создавалось как можно меньше массивов, ведь так?

Идея была в том, что бы создать временный двумерный массив result. В него циклически записывать результат слияния двух подмассивов из оригинальногго unsortArr. Когда первый круг слияния прошел, приравниваем наш unsortArr к result (в котором, как помним, хранится результат попарного слияния первого круга). Обновляем переменные (result) включительно, и повторяем шаги.

Реализация внизу где-то зациклена.

Может моя идея в целом неверное исполнение marge_sort? В сети много примеров на С/С++, но в контексте js это все немного не то. Или у меня где-то ошибка при работе с двумерными массивами?

Буду благодарна за подсказки, в глазах уже рябит.

console.log('Begin \n'); 
 
const unsortArr = [8, 5, 1, 7, 4, 9, 3, 10, 2, 6]; 
const length = unsortArr.length; 
 
function merge(arr) { 
  let l = arr.length; 
  for (let i = 0; i < l; i++) { 
    arr[i] = [arr[i]]; 
  } 
  return arr; 
} 
let l = Math.floor(unsortArr.length / 2); 
 
function sort(arr) { 
  var result = [], //массив для хранения отсортированых подмассивов 
      j = 0; // индекс вставки в результат отсортированного подмассива 
       
  //перебираем все подмассивы попарно 
  for (let i = 0; i <= l; i += 2) { 
    var leftIndex = 0, // индекс левого массива 
      rightIndex = 0; //индекс правого массива 
       
    console.log('\n' + 'lets start for ' + i); 
 
    // создаем подмассив в j ячейке 
    result[j] = new Array(); 
 
    //до тех пор, пока не 'сольётся' хотя бы один массив, проводить поэлементное сравнение двух подмассивов   
    while ((leftIndex <= arr[i].length) || (rightIndex <= arr[i + 1].length)) { 
      if (arr[i][leftIndex] > arr[i + 1][rightIndex]) { 
        result[j].push(arr[i + 1][rightIndex]); 
        result[j].push(arr[i][leftIndex]); 
        rightIndex++; 
      } 
      if (arr[i][leftIndex] < arr[i + 1][rightIndex]) { 
        result[j].push(arr[i][leftIndex]); 
        result[j].push(arr[i + 1][rightIndex]); 
        leftIndex++; 
      } 
      if (arr[i][leftIndex] === arr[i + 1][rightIndex]) { 
        result[j].push(arr[i][leftIndex]); 
        result[j].push(arr[i + 1][rightIndex]); 
        leftIndex++; 
        rightIndex++; 
      } 
    } // конец цикла while 
 
    //у одного из массивов мог остаться отсортированный "хвост" надо его найти и приклеить к результату 
    if (leftIndex !== arr[i].length - 1) { 
      result[j].concat(arr[i].slice(leftIndex)); 
    } 
    if (rightIndex !== arr[i + 1].length - 1) { 
      result[j].concat(arr[i + 1].slice(rightIndex)); 
    } 
    console.log('\n result j = ' + result[j]); 
    j++; 
 
  } 
   
   
  // arr = result; 
  return arr; 
//   if (length == arr[0].length ){ 
//   return arr; 
// } 
// else sort(arr); 
} 
 
console.log(merge(unsortArr)); 
 
console.log('\n' + sort(unsortArr) );