В чем ошибка программы сортировки?

143

30 ноября 2019, 00:00

Есть программа визуализации сортировки слиянием.
До этого реализовывал примерно также пузырьком, расческой и выбором, но только тут началась какая-то чертовщина. Сама функция работает, но не могу понять в чем дело

Это алгоритм

function mergeSort(arr, key) { 
	var result; 
 
	if (arr.length <= 1) { 
		return arr 
	} 
 
	const middle = Math.floor(arr.length / 2); 
    const left = arr.slice(0, middle); 
    const right = arr.slice(middle); 
 
	return merge(mergeSort(left), mergeSort(right), key); 
} 
 
function merge(left, right, key) { 
	var result = [], 
		i = j = 0; 
	if (!left) { 
		left = [] 
	} 
	if (!right) { 
		right = [] 
	} 
	while (i < left.length && j < right.length) { 
		result.push( 
			(left[i][key] < right[j][key]) ? 
				left[i++] : right[j++] 
		); 
	} 
	return [ 
		...result, 
		...left.slice(i), 
		...right.slice(j) 
	]; 
}

А это функция отрисовки

function draw() { 
	cleanWindow(true); 
	for (var i = 0; i < elements.length; i++) { 
		var x = elements[i].x, 
			y = elements[i].y, 
			height = elements[i].height, 
			h = elements[i].h, 
			s = elements[i].s, 
			l = elements[i].l; 
		c.beginPath(); 
		c.rect(i, y, 
			   1, -height); 
		c.fillStyle = `hsl(${h}, ${s}%, ${l}%`; 
		c.fill(); 
		c.closePath(); 
	} 
	 
	elements = mergeSort(elements, 'height'); 
}

Алгоритм возвращает отсортированный массив в этот же массив Keys нужна, так как в этой же программе сортирую не только по высоте, но и по цвету. В elements добавляется объект с координатами, но для удобства этого алгоритма, решил за х брать отсортированное положение индекса.

Вот весь код

<!DOCTYPE html> 
<html lang="en"> 
<head> 
	<meta charset="UTF-8"> 
	<title>Merge Sort</title> 
	<style> 
		* { 
			margin: 0; 
			padding: 0; 
			overflow: hidden; 
		} 
 
		canvas { 
			width: 100%; 
			height: 100%; 
		} 
	</style> 
</head> 
<body> 
	<canvas id="myCanvas"></canvas> 
	<script> 
		var canvas = document.getElementById("myCanvas"), 
	c = canvas.getContext('2d'), 
	x = 0, y = 0, 
	elements = [], 
	bgColor = '#000'; 
canvas.width = window.innerWidth; 
canvas.height = window.innerHeight; 
var k = 0; 
 
var ex = ey = 0; 
document.onclick = function(e) { // выводит текущие координаты при клике 
      ex = e.clientX; 
      ey = e.clientY; 
    }; 
 
 
cleanWindow(true); 
for (var i = 0; i <= canvas.width; i++) { 
	height = randInt(0, canvas.height); 
	elements.push({ 
		x: i, 
		y: canvas.height, 
		height: height, 
		// h: randRange(0, 360), 
		h: 0, 
		s: 100, 
		l: 50 
	}) 
	h = elements[i].h; 
	s = elements[i].s; 
	l = elements[i].l; 
	c.beginPath(); 
	c.rect(x, canvas.height, 
			1, -height); 
	c.fillStyle = `hsl(${h}, ${s}%, ${l}%`; 
	c.fill(); 
	c.closePath(); 
} 
 
setInterval(draw, 1); 
 
function draw() { 
	cleanWindow(true); 
	if (document.onclick && ex && ey) { 
		elements[ex].height = canvas.height-ey; 
	} 
	ex = ey = 0; 
	for (var i = 0; i < elements.length; i++) { 
		var x = elements[i].x, 
			y = elements[i].y, 
			height = elements[i].height, 
			h = elements[i].h, 
			s = elements[i].s, 
			l = elements[i].l; 
		c.beginPath(); 
		c.rect(i, y, 
			   1, -height); 
		c.fillStyle = `hsl(${h}, ${s}%, ${l}%`; 
		c.fill(); 
		c.closePath(); 
	} 
	 
	elements = mergeSort(elements, 'height'); 
 
} 
 
function mergeSort(arr, key) { 
	var result; 
 
	if (arr.length <= 1) { 
		return arr 
	} 
 
	const middle = Math.floor(arr.length / 2); 
    const left = arr.slice(0, middle); 
    const right = arr.slice(middle); 
 
	return merge(mergeSort(left), mergeSort(right), key); 
} 
 
function merge(left, right, key) { 
	var result = [], 
		i = j = 0; 
	if (!left) { 
		left = [] 
	} 
	if (!right) { 
		right = [] 
	} 
	while (i < left.length && j < right.length) { 
		result.push( 
			(left[i][key] < right[j][key]) ? 
				left[i++] : right[j++] 
		); 
	} 
	return [ 
		...result, 
		...left.slice(i), 
		...right.slice(j) 
	]; 
} 
 
 
function cleanWindow(visible) { 
	if (visible) { 
		c.beginPath(); 
		c.rect(0, 0, 
			   canvas.width, canvas.height); 
		c.fillStyle = bgColor; 
		c.fill(); 
		c.closePath(); 
	} 
} 
 
function randInt(min, max, except) { 
	if (except !== undefined) { 
		var result = Math.floor(min + Math.random() * (max - min)); 
		if (result !== except) { 
			return result; 
		} 
		return randInt(min, max, except); 
	} 
	return Math.floor(min + Math.random() * (max - min)); 
} 
 
function randRange(min, max, step) { 
	if (step !== undefined) { 
		var result = Math.floor(min + Math.random() * (max + 1 - min)); 
		if (result % step !== 0) { 
			return randRange(min, max, step); 
		} else { 
			return result 
		} 
	} 
	return Math.floor(min + Math.random() * (max + 1 - min)); 
} 
	</script> 
</body> 
</html>