Very surprising result though! Multiplication is easier than sorting.

zeroonetwothree 3 hours ago | parent | next [-]

Then 'n' means kind of different things for sorting vs. multiplication though. For example for sorting we assume constant time comparison, which doesn't make sense inputs of O(n) bits

	▲	sobellian an hour ago \| parent [-]
		If you sort n k-bit items for a total time of O(nk logn), that scales more poorly in n than multiplying n-word integers. Of course if k is constant you can do radix sort, but I genuinely don't know under what conditions radix sort is more/less galactic than this multiplication algorithm.

▲

senderista 3 hours ago | parent | prev [-]

It would be absolutely unbelievable if such an improvement were practical.