mergeSort

合併排序

by Chris_Walter

JavaScript

class ArrayList{
  constructor(){
	  this.array = [];
	}
	toString(){
	  return this.array.join();
	}
	insert(item){
	  this.array.push(item);
	}
	merge(left, right){
	  console.log(`mergeL: ${left}`);
		console.log(`mergeR: ${right}`);
	  const result = [];
		let al=0;
		let ar=0;
		while(al < left.length && ar < right.length){
		  if(left[al] < right[ar]){
			  result.push(left[al]);
				al++
			} else{
			  result.push(right[ar]);
				ar++
			}
		}
		//return result.concat(left.slice(al)).concat(right.slice(ar));
		return [...result, ...left.slice(al), ...right.slice(ar)];
	}
	mergeSortRecursion(array){
	  let length = array.length;
	  if(length === 1){
		  return array;
		}
		let mid = Math.floor(length / 2);
		console.log(`mid: ${mid}`)
		let left = array.slice(0, mid);
		let right = array.slice(mid, length);
		console.log(`mergeRecLeft: ${left}`);
		console.log(`mergeRecRight: ${right}`);
		return this.merge(this.mergeSortRecursion(left), this.mergeSortRecursion(right));
	}
	mergeSort(){
	  this.array = this.mergeSortRecursion(this.array);
	}
}


const nonSortedArray = (arraySize) => {
  const array = new ArrayList();
	for(let i=arraySize; i>0; i--){
	  array.insert(i);
	}
	console.log(`未使用合併排序前: ${array}`);
	array.mergeSort();
	console.log(`合併排序後: ${array}`);
}

nonSortedArray(4);