> Starting from an array A that has n distinct integers

I don't know in what ways they are differents, but these programs were not designed to work with duplicates in the input. This probably explains the results.