but it is correct to call the complexity O(n), it will scale linearly with the number of elements

Actually, probably not true. As far as I can tell @array3 = sort @array3; is O(N*log N) so it's unlikely the overall code is better than that.