설명 :

위키 피 디아 (Wikipedia)에 따르면 "Merge sort (대개 철자가있는 mergesort)는 O (n log n) 비교 기반 정렬 알고리즘입니다. 대부분의 구현은 안정된 정렬을 생성합니다. 즉, 구현시 정렬 된 출력에서 ​​동일한 요소의 입력 순서가 유지됩니다. "

코드 :

function merge_sort(left_part,right_part) 
{
	var i = 0;
	var j = 0;
	var results = [];

	while (i < left_part.length || j < right_part.length) {
		if (i === left_part.length) {
			// j is the only index left_part
			results.push(right_part[j]);
			j++;
		} 
      else if (j === right_part.length || left_part[i] <= right_part[j]) {
			results.push(left_part[i]);
			i++;
		} else {
			results.push(right_part[j]);
			j++;
		}
	}
	return results;
}

console.log(merge_sort([1,3,4], [3,7,9]));

결과 :

1,3,3,4,7,9