Sorting array of strings (with repetitions) according to a given ordering

We get two arrays:

ordering = ["one", "two", "three"] 

and

input = ["zero", "one", "two", "two", "three", "three", "three", "four"]; 

We want to find the array output so that

output = ["one", "two", "two", "three", "three", "three", "zero", "four"] // or output = ["one", "two", "two", "three", "three", "three", "four", "zero"] 

The strings (with possible repetitions) should be sorted as in the ordering array. Not found/contained strings should be put at the end of the new array and their order doesn’t matter.

The $ n^{2}$ solution is obvious, can we do better? The memory doesn’t matter and it doesn’t have to be an in-place algorithm.