UE3 talk:Insertion Sort Macro

Possible Optimization

Right now within the inner loop it compares the two elements 3 times. A == B, A > B, B > A. But general rules dictate, that if !(A > B), and !(B > A) then it must be A == B, right? (As also explained in the document). So the first compare is actually not needed, thus reducing the requirement for a additional operator to implement for custom types. Is my assumption correct? --elmuerte 19:49, 16 September 2009 (UTC)

Whenever I implement a binary search, I usually just test for two of the three cases, either < and >, leaving == up to the else, or == right at the beginning and only either < or >, handling the other in the else. Only float NaN values might break things as NaN <=> X is always false, even if X also is NaN. —Wormbo 05:47, 17 September 2009 (UTC)

I've changed the algorithm to not use the equals operator, if !(A > B || B > A) then it doesn't really matter which one comes first, so it shouldn't affect sorting much anyway. Also, the new code makes the operator usage a parameter so you can now easily change the operator used and perform reverse sorting. --elmuerte 18:42, 17 September 2009 (UTC)

Instead of using array.Insert(index, 1) and array[index] = value, array.InsertItem(index, value) might be a bit more efficient. —Wormbo 16:51, 26 September 2009 (UTC)