Why is this seemingly simple insert trigger function causing deadlocks?
Under heavy concurrent write access, the defense against deadlocks is to process rows in consistent order in all writing queries.

You may have sorted rows properly in all your writing queries to the table tweet- did you? (I know about that table from your related question.)

And you are obviously sorting rows to be "upserted" in url_starting in the trigger function.

That should do it for transactions inserting a single row in tweet with multiple URLs to be upserted in url_starting.

But while inserting multiple rows to tweet, each with an arbitrary array of URLs, rows to be upserted in url_starting are still in inconsistent order for the transaction. URLs are only sorted per row in tweet, not for the whole transaction (or even command). You would need to unnest all URLs of the same INSERT, sort them consistently, and then upsert url_starting. This cannot be achieved with a trigger FOR EACH ROW. I don't think you can solve this at all with your current approach while inserting multiple rows with arbitrary arrays of URLs. Concurrent write access to both tables is inherently conflicting.

Single-row inserts to tweet should be fine (each in its own transaction) - though possibly substantially more expensive. Maybe you can get rid of the trigger completely and reorganize the workflow (with data-modifying CTEs): write a sorted list of URLs to url_starting, then write to tweet ...

Arrays are often problematic in a relational table design. Full normalization might be another approach - replacing the array column with a related table. Not sure if that's the way ...

Or you keep your transactions as short and fast as possible, making deadlocks the rare exception, and prepare your application to retry in case of an error.