Old Norse alternate titles
If the sagas, written in Old Norse are any indication, then the title (or occupational byname) comes after your first name. Then comes a descriptive byname, a locative, and finally a patronymic (or, more rarely, matronymic). So while in English his name is King Harald Fine-hair, in Old Norse he is Haraldr konungr inn hárfagri. Similarly, the 13th century King Haakon Haakonarson is Hákon konungr Hákonarson in Old Norse. It also seems to be generally written in lower-case, too.