Alternative to "Sort" as a PowerShell verb?

I think something like ConvertTo-SortedVersionLabels, while a little bit awkward, uses an approved and non-reserved verb but is still clear.

You could also make sorting a parameter to a different function, like Get-VersionLabels -Sorted.

How you would work that in depends on your module as a whole and whether you have such a function to modify. It's unclear from your current post, but if you edit it with more details we might be able to provide more suggestions.

The core of this issue will generate opinionated results. This creates a conundrum since you are looking for something specific that the current answers have been unable to address. I understand that you are looking for a solution that logically fits your function while being in the standard verb list, which is admirable. To continue from an earlier comment I made I am going to try and state a case for all the approved verbs that might fit your situation. I will refer to the Approved Verbs List linked in your question frequently and will use "AVL" for brevity going forward.

1. Group: The comments on the AVL refers to using this in place of Arrange. Arrange being a synonym for Sort would be a good fit. Sticking with the recommendation then we should use Group
2. Set: It is a synonym for Sort. However, in the AVL, it is associated with Write, Reset, Assign, or Configure which are not related to your cmdlet. Still, it is in the list and could fit if you are willing to put aside the discombobulation that it creates with existing PowerShell cmdlets.
3. I dont really have a number 3.
4. Update: This is a weak case but the AVL refers its use as a way to maintain [a cmdlets] state [and] accuracy.
5. Order/Organize: Not in the AVL but I find these very fitting and dont currently conflict with any existing verbs.

Ultimately, AVL be damned and do whatever you want. Sort is a very good fit for what you are trying to do. You can also just use -DisableNameChecking when importing your module. It is only a warning after all. Briatist's answer is also good in my opinion.

Bonus from comments

Not that you asked for it, but when you said we have to enable name checking I thought about this. Just for fun!

$reservedVerbs = "ForEach","Format","Group","Sort","Tee"
$approvedVerbList = (Get-Verb).Verb

Get-Command -Module  Microsoft.WSMan.Management | ForEach-Object{
    If ($approvedVerbList -notcontains ($_.Name -split "-")[0]){
        Write-Warning "$($_.Name) does not use an approved verb."
    }

    If ($reservedVerbs -contains ($_.Name -split "-")[0]){
        Write-Warning "$($_.Name) is using a reserved verb."
    }
}

Whenever I need a verb that is not an approved PowerShell verb, I use Invoke-* instead. So in your case, you could name it Invoke-SortVersionLabels