Sorting a set of CSS selectors on the basis of specificity

How can a set of CSS selectors be sorted on the basis of CSS specificity in a JS function?

function SortByCssSpecificity(input_array_of_css_selectors) {
  ...
  return sorted_array_of_css_selectors;
}

From the Selectors level 3 spec:

A selector's specificity is calculated as follows:

• count the number of ID selectors in the selector (= a)
• count the number of class selectors, attributes selectors, and pseudo-classes in the selector (= b)
• count the number of type selectors and pseudo-elements in the selector (= c)
• ignore the universal selector

Selectors inside the negation pseudo-class [:not()] are counted like any other, but the negation itself does not count as a pseudo-class.

Concatenating the three numbers a-b-c (in a number system with a large base) gives the specificity.

Examples:

*               /* a=0 b=0 c=0 -> specificity =   0 */
LI              /* a=0 b=0 c=1 -> specificity =   1 */
UL LI           /* a=0 b=0 c=2 -> specificity =   2 */
UL OL+LI        /* a=0 b=0 c=3 -> specificity =   3 */
H1 + *[REL=up]  /* a=0 b=1 c=1 -> specificity =  11 */
UL OL LI.red    /* a=0 b=1 c=3 -> specificity =  13 */
LI.red.level    /* a=0 b=2 c=1 -> specificity =  21 */
#x34y           /* a=1 b=0 c=0 -> specificity = 100 */
#s12:not(FOO)   /* a=1 b=0 c=1 -> specificity = 101 */

(Selectors level 4, published after this answer, adds another layer of complexity to specificity thanks to the introduction of some new selectors that is currently outside this answer's scope.)

Here's a pseudocode implementation to get you started, it is nowhere near perfect but I hope it's a reasonable starting point:

function SortByCssSpecificity(selectors, element) {
    simple_selectors = [][]
    for selector in selectors {
        // Optionally pass an element to only include selectors that match
        // The implementation of MatchSelector() is outside the scope
        // of this answer, but client-side JS can use Element#matches()
        // https://developer.mozilla.org/en-US/docs/Web/API/Element/matches
        if (element && !MatchSelector(selector, element)) {
            continue
        }

        simple_selectors[selector] = ParseSelector(selector)
        simple_selectors[selector] = simple_selectors[selector].filter(x | x != '*')

        // This assumes pseudo-elements are denoted with double colons per CSS3
        // A conforming implementation must interpret
        // :first-line, :first-letter, :before and :after as pseudo-elements
        a = simple_selectors[selector].filter(x | x ^= '#').length
        b = simple_selectors[selector].filter(x | x ^= '.' or x.match(/^:[^:]+/) or x.match(/^\[.+\]$/)).length
        c = simple_selectors[selector].length - (a + b)

        simple_selectors[selector][count] = parseInt('' + a + b + c)
    }

    return simple_selectors.sort(x, y | x[count] < y[count])
}

function ParseSelector(selector) {
    simple_selectors = []
    // Split by the group operator ','
    // Split each selector group by combinators ' ', '+', '~', '>'
    // :not() is a special case, do not include it as a pseudo-class

    // For the selector div > p:not(.foo) ~ span.bar,
    // sample output is ['div', 'p', '.foo', 'span', '.bar']
    return simple_selectors
}