# Sorting

var arr = [6, 3, 8, 4, 1, 9, 2, 5, 7, 0];

function MergeSort(arr) {
  this.arr = null;

  if (arr instanceof Array) {
    this.arr = arr;
    return this.sort(arr);
  }
}

MergeSort.prototype = (function () {
  function sort(arr) {
    if (typeof arr === 'undefined' || !(arr instanceof Array)) {
      if (!(this.arr instanceof Array)) {
        throw new Error('Array object is not exist');
      }
      arr = this.arr;
    }

    if (arr.length === 1) {
      return arr;
    }

    var mid = Math.floor(arr.length / 2),
      left = arr.slice(0, mid),
      right = arr.slice(mid);

    return merge(sort(left), sort(right));
  }

  function merge(left, right) {
    var answer = [],
      leftLength = left.length,
      rightLength = right.length,
      leftIdx = 0,
      rightIdx = 0;

    while (leftIdx < leftLength && rightIdx < rightLength) {
      if (left[leftIdx] < right[rightIdx]) {
        answer.push(left[leftIdx]);
        leftIdx++;
      } else {
        answer.push(right[rightIdx]);
        rightIdx++;
      }
    }

    return answer.concat(left.slice(leftIdx), right.slice(rightIdx));
  }

  return {
    sort: sort
  };
}());

console.log(new MergeSort(arr));

var ms = new MergeSort();

console.log(ms.sort(arr));

const array = [5, 3, 1, 4, 2];

let len = array.length, i = 1, j, temp;

for (; i < len; ++i) {
  temp = array[i];
  j = i;

  while (j > 0 && array[j - 1] > temp) {
    array[j] = array[j - 1];

    j--;
    cnt++;
  }

  array[j] = temp;
}

console.log(array.join(' '));