bash - recursive sorting

[heliumhe]

Hi, how can I, in a bash script, sort a file like

a
b
c
d
e
f

accordring to some rules in another file like

c='d e' #d and e must come before c
e='f a b' #f, a and b must come before e

so that the end result becomes

a
b
d
f
e
c

[Kloschüssel]

Unfortunatly, you cannot use sort as that doesn't support a self implemented comparator. You could, however, implement a the insert-sort algorithm. In pseudo-code this should look somewhat alike:

while read line do
  while read tmpline do
    # compare $line and $tmpline
    if smaller do
      $tmpline >> tmpfilePre
    else
      $tmpline >> tmpfilePost
  done < tmpfile
  # merge data
  tmpfilePre > tmpfile
  $line >> tmpfile
  tmpfilePost >> tmpfile
  # remove temp files
done < input
tmpfile > outfile

PS: This may should be a doable task for awk.
PPS: I could think of an merge-sort implementation by using wc and split just alike the above code which should perform faster for big files.

Oh, it came into my mind that there's an even neater solution:

# prefix each line with an alpha-numerical sortable identifier
# sort file by using the sortable prefix
# strip prefixes and write result to output file