
Sorting Algorithm

This is a sorting algorithm.   It may be applied to a set of data in order to sort it.    
For comparing various sorts, see compare sorts.  
For other sorting algorithms,   see sorting algorithms,   or:

O(n logn) sorts
Heap sort |
Merge sort |
Patience sort |
Quick sort
O(n log2n) sorts
Shell Sort
O(n2) sorts
Bubble sort |
Cocktail sort |
Cocktail sort with shifting bounds |
Comb sort |
Cycle sort |
Gnome sort |
Insertion sort |
Selection sort |
Strand sort
other sorts
Bead sort |
Bogo sort |
Common sorted list |
Composite structures sort |
Custom comparator sort |
Counting sort |
Disjoint sublist sort |
External sort |
Jort sort |
Lexicographical sort |
Natural sorting |
Order by pair comparisons |
Order disjoint list items |
Order two numerical lists |
Object identifier (OID) sort |
Pancake sort |
Quickselect |
Permutation sort |
Radix sort |
Ranking methods |
Remove duplicate elements |
Sleep sort |
Stooge sort |
[Sort letters of a string] |
Three variable sort |
Topological sort |
Tree sort


Natural sorting is the sorting of text that does more than rely on the
order of individual characters codes to make the finding of
individual strings easier for a human reader.

There is no "one true way" to do this, but for the purpose of this task 'natural' orderings might include:

1. Ignore leading, trailing and multiple adjacent spaces
2. Make all whitespace characters equivalent.
3. Sorting without regard to case.
4. Sorting numeric portions of strings in numeric order.
 That is split the string into fields on numeric boundaries, then sort on each field, with the rightmost fields being the most significant, and numeric fields of integers treated as numbers.
 foo9.txt before foo10.txt
 As well as ... x9y99 before x9y100, before x10y0
 ... (for any number of groups of integers in a string).
5. Title sorts: without regard to a leading, very common, word such
 as 'The' in "The thirty-nine steps".
6. Sort letters without regard to accents.
7. Sort ligatures as separate letters.
8. Replacements:
 Sort German eszett or scharfes S (ß)       as   ss
 Sort ſ, LATIN SMALL LETTER LONG S     as   s
 Sort ʒ, LATIN SMALL LETTER EZH           as   s
  ∙∙∙ 
Task Description
 Implement the first four of the eight given features in a natural sorting routine/function/method...
 Test each feature implemented separately with an ordered list of test strings from the   Sample inputs   section below,   and make sure your naturally sorted output is in the same order as other language outputs such as    Python. 
 Print and display your output.
 For extra credit implement more than the first four.


Note:   it is not necessary to have individual control of which features are active in the natural sorting routine at any time.



Sample input

• Ignoring leading spaces.                       Text strings:   ['ignore leading spaces:  2-2',
                                                                  'ignore leading spaces:  2-1', 
                                                                  'ignore leading spaces:  2+0',
                                                                  'ignore leading spaces:  2+1']

• Ignoring multiple adjacent spaces (MAS).       Text strings:   ['ignore MAS spaces:  2-2', 
                                                                  'ignore MAS spaces:  2-1', 
                                                                  'ignore MAS spaces:  2+0', 
                                                                  'ignore MAS spaces:  2+1']

• Equivalent whitespace characters.              Text strings:   ['Equiv.  spaces:     3-3', 
                                                                  'Equiv. \rspaces:    3-2', 
                                                                  'Equiv. \x0cspaces:  3-1', 
                                                                  'Equiv. \x0bspaces:  3+0', 
                                                                  'Equiv. \nspaces:    3+1', 
                                                                  'Equiv. \tspaces:    3+2']

• Case Independent sort.                         Text strings:   ['cASE INDEPENDENT:  3-2', 
                                                                  'caSE INDEPENDENT:  3-1', 
                                                                  'casE INDEPENDENT:  3+0', 
                                                                  'case INDEPENDENT:  3+1']
  
• Numeric fields as numerics.                    Text strings:   ['foo100bar99baz0.txt', 
                                                                  'foo100bar10baz0.txt', 
                                                                  'foo1000bar99baz10.txt', 
                                                                  'foo1000bar99baz9.txt']

• Title sorts.                                   Text strings:   ['The Wind in the Willows', 
                                                                  'The 40th step more', 
                                                                  'The 39 steps', 
                                                                  'Wanda']

• Equivalent accented characters (and case).     Text strings:   [u'Equiv. \xfd accents:  2-2', 
                                                                  u'Equiv. \xdd accents:  2-1', 
                                                                  u'Equiv.  y accents:    2+0', 
                                                                  u'Equiv.  Y accents:    2+1']

• Separated ligatures.                           Text strings:   [u'\u0132 ligatured ij', 
                                                                   'no ligature']

• Character replacements.                        Text strings:   [u'Start with an \u0292:  2-2', 
                                                                  u'Start with an \u017f:  2-1', 
                                                                  u'Start with an \xdf:    2+0', 
                                                                  u'Start with an  s:      2+1']





use AppleScript version "2.4" -- OS X 10.10 (Yosemite) or later
use framework "Foundation"
use sorter : script "Custom Iterative Ternary Merge Sort" -- <https://macscripter.net/viewtopic.php?pid=194430#p194430>
 
on naturalSort(listOfText)
    -- Produce versions of the strings for sorting purposes, doctored to get round
    -- the situations AppleScript's comparison attributes don't handle naturally.
    script o
        property input : listOfText
        property doctored : {}
    end script
    set regex to current application's NSRegularExpressionSearch
    repeat with i from 1 to (count listOfText)
        set thisString to (current application's class "NSMutableString"'s stringWithString:(item i of o's input))
        -- AppleScript's 'ignoring white space' setting ignores ALL white space. So, since the existence of
        -- white space between words has to be considered, physically remove or alter any to be ignored.
        -- Firstly reduce runs of any type of white space to single 'space' characters.
        tell thisString to replaceOccurrencesOfString:("\\s++") withString:(space) options:(regex) range:({0, its |length|()})
        -- Then remove any leading and/or trailing spaces.
        tell thisString to replaceOccurrencesOfString:("^ | $") withString:("") options:(regex) range:({0, its |length|()})
        -- Move any instance of "The ", "A ", or "An " at the front of a string to the end assuming the string to be a title.
        -- This allows the article to act as a tie-breaker if necessary.
        tell thisString to replaceOccurrencesOfString:("^(?i)(The|An?) (.++)$") withString:("$2 $1") options:(regex) ¬
            range:({0, its |length|()})
        -- For the sake of this task, replace any instances of "ſ" or "ʒ" with "s".
        tell thisString to replaceOccurrencesOfString:("[\\u0292\\u017f]") withString:("s") options:(regex) ¬
            range:({0, its |length|()})
        set end of o's doctored to thisString as text
    end repeat
 
    -- Set AppleScript's string comparison attributes for the sort.
    -- Ligatures are always compared by their component characters and AppleScript has no setting to change this.
    -- 'Numeric strings' are runs of digit characters only.
    -- The white space, hyphens, and case settings here are the defaults,
    -- but are set explicitly in case this handler's called from a different setting.
    considering numeric strings, white space and hyphens but ignoring diacriticals, punctuation and case
        -- Sort items 1 thru -1 of the doctored strings, rearranging the original list in parallel.
        tell sorter to sort(o's doctored, 1, -1, {slave:{listOfText}})
    end considering
 
    return listOfText
end naturalSort
 
(* Tests: *)
-- Leading, trailing, and multiple white spaces ignored:
naturalSort({"  ignore superfluous spaces: 1-3", "ignore superfluous spaces: 1-1", "  ignore superfluous    spaces: 1-2", ¬
    "   ignore superfluous spaces: 1-4", "ignore superfluous spaces: 1-7", "ignore superfluous    spaces: 1-5   ", ¬
    "ignore superfluous   spaces: 1-6", "   ignore    superfluous     spaces: 1-8"})
--> {"ignore superfluous spaces: 1-1", "  ignore superfluous    spaces: 1-2", "  ignore superfluous spaces: 1-3", "   ignore superfluous spaces: 1-4", "ignore superfluous    spaces: 1-5   ", "ignore superfluous   spaces: 1-6", "ignore superfluous spaces: 1-7", "   ignore    superfluous     spaces: 1-8"}
 
-- All white space characters treated as equivalent:
naturalSort({"Equiv. spaces: 2-6", "Equiv." & return & "spaces: 2-5", "Equiv." & (character id 12) & "spaces: 2-4", ¬
    "Equiv." & (character id 11) & "spaces: 2-3", "Equiv." & linefeed & "spaces: 2-2", "Equiv." & tab & "spaces: 2-1"})
(* -->
{"Equiv.    spaces: 2-1", "Equiv.
spaces: 2-2", "Equiv.�spaces: 2-3", "Equiv.�spaces: 2-4", "Equiv.
spaces: 2-5", "Equiv. spaces: 2-6"}
*)
 
-- Case ignored. (The order would actually be the same with case considered,
-- because case only decides the issue when strings are otherwise identical.)
naturalSort({"cASE INDEPENDENT: 3-1", "caSE INDEPENDENT: 3-2", "CASE independent: 3-3", "casE INDEPENDENT: 3-4", ¬
    "case INDEPENDENT: 3-5"})
--> {"cASE INDEPENDENT: 3-1", "caSE INDEPENDENT: 3-2", "CASE independent: 3-3", "casE INDEPENDENT: 3-4", "case INDEPENDENT: 3-5"}
 
-- Numerics considered by number value:
naturalSort({"foo1000bar99baz10.txt", "foo100bar99baz0.txt", "foo100bar10baz0.txt", "foo1000bar99baz9.txt"})
--> {"foo100bar10baz0.txt", "foo100bar99baz0.txt", "foo1000bar99baz9.txt", "foo1000bar99baz10.txt"}
 
-- Title sort:
naturalSort({"The Wind in the Willows", "The 40th Step More", "A Matter of Life and Death", "The 39 steps", ¬
    "An Inspector Calls", "Wanda"})
--> {"The 39 steps", "The 40th Step More", "An Inspector Calls", "A Matter of Life and Death", "Wanda", "The Wind in the Willows"}
 
--> Diacriticals (and case) ignored:
naturalSort({"Equiv. " & (character id 253) & " accents: 6-1", "Equiv. " & (character id 221) & " accents: 6-3", ¬
    "Equiv. y accents: 6-4", "Equiv. Y accents: 6-2"})
--> {"Equiv. ý accents: 6-1", "Equiv. Y accents: 6-2", "Equiv. Ý accents: 6-3", "Equiv. y accents: 6-4"}
 
-- Ligatures:
naturalSort({(character id 306) & " ligatured", "of", "ij no ligature", (character id 339), "od"})
--> {"Ĳ ligatured", "ij no ligature", "od", "œ", "of"}
 
-- Custom "s" equivalents and Esszet (Esszet normalises to ss):"
naturalSort({"Start with an " & (character id 658) & ": 8-1", "Start with an " & (character id 383) & ": 8-2", ¬
    "Start with an " & (character id 223) & ": 8-3", "Start with an s: 8-4", "Start with an ss: 8-5"})
--> {"Start with an ʒ: 8-1", "Start with an ſ: 8-2", "Start with an s: 8-4", "Start with an ß: 8-3", "Start with an ss: 8-5"}