Sorting a list by Rules

I have a list which I need to sort.

['Product ED', 'Product CX', 'Product XY', 'Product ED']

This list has to be sorted after a defined rule:

['CX', 'XY', 'ED']

So, in the end the list has to be ordered after this rule, like this:

['Product CX', 'Pr开发者_Python百科oduct XY', 'Product ED', 'Product ED']

How would you implement an algorithm like this?

EDIT: Well, I came up with a simple idea right after I wrote this question...

Here it is:

var l = ['Product ED', 'Product CX', 'Product XY', 'Product ED'];
var rules = ['CX', 'XY', 'ED'];

l.sort(function(a, b) {
    return rules.indexOf(a.replace(/^Product /, '')) > rules.indexOf(b.replace(/^Product /, ''));
})

['Product CX', 'Product XY', 'Product ED', 'Product ED']

---

Well, the quick & dirty way would be to prepend each value with a sort key. '1Product CX', '2Product XY' etc., sort it, then strip them off afterwards.

Just make sure the sort key you append is the same length, if you've got more than 10, you'll need '01', '02' etc.

If you want to do it properly, then you'll need to define a compare function and pass that to the 'sort' function as a parameter: http://www.w3schools.com/jsref/jsref_sort.asp

---

More formally, you can define a comparison function which takes two elements from the list to be sorted, the rule list, and then return 1 if the first item is greater than the second (according to the rules) and a -1 if it is less, and a 0 if they are the same. Then, any comparison-based sort will work.

Complexity: T(n) = 2T(n/2) + O(nm) =? O(m n log n) is possible with e.g. mergesort... right? (note: n is the number of elements in the list to be sorted, m the size of the rule set).

---

jsFiddle

    var list = ['Product ED', 'Product CX', 'Product XY', 'Product ED'];
    var rule = ['CX', 'XY', 'ED'];

    list.sort(function(a, b) {
        var aIndex, bIndex;
        for (var i = 0; i < rule.length; i++) {
            var aMatch = a.match(rule[i]);
            var bMatch = b.match(rule[i]);
            if (aMatch && aMatch.length > 0) {
                aIndex = rule.indexOf(aMatch[0])
            }
            if (bMatch && bMatch.length > 0) {
                bIndex = rule.indexOf(bMatch[0]);
            }

            if (bIndex && aIndex) {
                continue;
            }
        }

        if (aIndex < bIndex) return -1;
        else if (aIndex > bIndex) return 1;
        else return 0;
    })

    console.log(list)