Joe Joe - 1 month ago 7
Javascript Question

Fuzzy sorting algorithm merge stability

Context



I am implementing a psychological test whereby a user is presented with pairs of images an has to indicate which they prefer. They respond to their preference with either the A or L key. If the number of images is quite large then comparing all possible pairs is rather demanding upon the individual (O(n^2)).

Question



I have hacked the merge-sort algorithm here to dramatically reduce the number of comparisons. The result is the following:

function mergeSort(arr)
{
if (arr.length < 2)
return arr;

var middle = parseInt(arr.length / 2);
var left = arr.slice(0, middle);
var right = arr.slice(middle, arr.length);

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


function merge(left, right)
{
var result = [];

while (left.length && right.length) {
if (getUserPreference(left[0],right[0])) {
result.push(left.shift());
} else {
result.push(right.shift());
}
}

while (left.length)
result.push(left.shift());

while (right.length)
result.push(right.shift());

return result;
}


where the function
getUserPreference
delegates to the user. I have run multiple simulations (where the response can accidentally be "wrong" ~1/3 of the time, and by "wrong" I mean not input their true preference by hitting the wrong key) and the sort appears to perform well according to the following criteria:


  • Output results are close enough to the user preference (simulated).

  • The algorithm stops in good time. ~20 steps for a list of 10 items.



What I would like to know is if the algorithm whizzkids out there can tell me if there is any chance that this algorithm will completely fail to either stop or approximate the input solutions.

Answer

Is there any chance that this algorithm will completely fail to stop?

No. The algorithm always halts, no matter how bad/wrong/unfortunate the comparsisons are.

The algorithm stops in good time. ~20 steps for a list of 10 items.

For 10 items, the best case is 15 comparisons, the worst case is 25 comparisons. In general, merge sort takes on average O(n log n) steps.

Is there any chance that this algorithm will completely fail to approximate the input solutions

That depends a lot on your definition of "close enough to the user preference". And probably an important mistake would be to assume that user preference is a transitive relation at all.