MergeSort reversing order of elements

Saeris

I've implemented a custom version of MergeSort for one of my addons, but it exhibits some odd behaviour. Say each element in the array has two properties: name and rarity. If I first sort by name (alphabetically) and then by rarity, the names within each rarity will be reversed. If I do another pass by rarity, the names will reverse again, and so on and so on.

Here's the Lua code, adapted from this.

local type = type;
local l_array, l_tempArray, l_comparison, l_isKey, l_reverse;
local l_SortAndMerge;

function l_MergeSort(array, comparison, reverse)
	l_array = array;
	l_tempArray = {};
	l_comparison = comparison;
	l_isKey = (type(comparison) ~= "function");
	l_reverse = ((reverse and true) or false);
	
	l_SortAndMerge(1, (#array + 1));
	
	l_array = nil;
	l_tempArray = nil;
	l_comparison = nil;
	l_isKey = nil;
	l_reverse = nil;
end


do
	local mathfloor = math.floor;

	function l_SortAndMerge(left, right)
		if (right == (left + 1)) then
			return;
		end
		
		local length = (right - left);
		local middle = (left + mathfloor(length / 2));
		
		l_SortAndMerge(left, middle);
		l_SortAndMerge(middle, right);
		
		local leftMobile = left;
		local rightMobile = middle;
		local takeFromLeft;
		local leftValue, rightValue;
		for index = 1, length, 1 do
			if (leftMobile < middle) then
				if (rightMobile == right) then
					leftValue = l_array[leftMobile];
					takeFromLeft = true;
				else
					leftValue = l_array[leftMobile];
					rightValue = l_array[rightMobile];
					if (l_isKey == true) then
						if (l_reverse == true) then
							takeFromLeft = (rightValue[l_comparison] < leftValue[l_comparison]);
						else
							takeFromLeft = (leftValue[l_comparison] < rightValue[l_comparison]);
						end
					else
						if (l_reverse == true) then
							takeFromLeft = l_comparison(rightValue, leftValue);
						else
							takeFromLeft = l_comparison(leftValue, rightValue);
						end
					end
				end
			else
				rightValue = l_array[rightMobile];
				takeFromLeft = false;
			end
			if (takeFromLeft) then
				l_tempArray[index] = leftValue;
				leftMobile = (leftMobile + 1);
			else
				l_tempArray[index] = rightValue;
				rightMobile = (rightMobile + 1);
			end
		end
		
		for index = left, (right - 1), 1 do
			l_array[index] = l_tempArray[(1 + index) - left];
		end
	end
end

In the case I described, the function is being called in this order:

l_MergeSort(resultsArray, "name", false);
l_MergeSort(resultsArray, "rarity", false);
l_MergeSort(resultsArray, "rarity", false);

Any ideas what's going on?

Doc

that's a wicked huge merge sort.

Saeris

What, the number of lines? I guess so. A lot of the lines are there to increase efficiency (the upvalues) or add functionality (the reverse/comparison checks) for my particular application. It certainly runs nicely, and creates very little garbage. It's just got this one odd bug.

Smasher

Change the < in "takeFromLeft = (leftValue[l_comparison] < rightValue[l_comparison]);" to <=, and likewise for the other similar statements.

Right now, when they're equal in the attribute being compared it swaps the two elements rather than keeping them in the same order.

Saeris

That was indeed the problem, thanks.