Sorting array of strings such that substrings of any other string will comes later

Sort algorithms are based on comparing pairs of values. Often programming languages allow to provide the built-in sort-method with a comparator function, which should take two arguments, and return an integer value indicating their relative order (-1, 0 or 1).

So define the comparator as follows:

compare(a, b):
    if a is substring of b then return 1
    if b is substring of a then return -1
    if a < b then return -1
    if a > b then return 1
    return 0

This substring-test should first check the length of the two strings to potentially avoid a scan of the strings. Because when a.length > b.length, then a cannot be a substring of b. Or you could also explicitly write:

compare(a, b):
    if a.length <= b.length and a is substring of b then return 1
    if a.length >= b.length and b is substring of a then return -1
    if a < b then return -1
    if a > b then return 1
    return 0

If the target programming language does not offer this possibility, then you should write your own sorting function (like QuickSort), and make sure it can use such a comparator, so that (starting from a standard implementation) you would replace:

 if a < b

with:

 if compare(a, b) < 0

...etc.

Transitivity of the relationship

Let's assume for a moment that the relationship that is encoded in the compare function is not transitive, so that we could find three strings a, b and c for which:

• compare(a, b) < 0
• compare(b, c) < 0
• but also: compare(c, a) <= 0

First, note what this says about the lengths of the three strings:

• compare(a, b) < 0 implies that a.length >= b.length
• compare(b, c) < 0 implies that b.length >= c.length
• compare(c, a) <= 0 implies that c.length >= a.length

From the first two we conclude that a.length >= c.length, and combining that with the third, we can conclude all three strings have the same length.

So now we have:

• compare(a, b) < 0 implies that a is alphabetically ordered before b
• compare(b, c) < 0 implies that b is alphabetically ordered before c
• compare(c, a) <= 0 implies that c is alphabetically ordered before a, or is equal to a.

This leads to a contradiction. And so we must conclude that the relationship is transitive.