As Anonymous said use merge sort and increment a count whenever you merge from the right array into the main array when there are still elements remaining in the left array. This indicates an element is out of order. An extension of this problem is counting the number of inversions in an array. http://stackoverflow.com/questions/337664/counting-inversions-in-an-array

I'm curious about how do you define "out of order"? For example, for array [10,1,2,3,4,5,6,7,8,9], by what's algorithm the number will be 10, but by e's algorithm the number will be just 1

I think this question is just a variation of finding largest increasing sub-sequence. Find its size (say k) Ans is n-k

You mean how many elements are not in the place they should be after they are sorted or what? If so just make a duplicate array and sort it, then go through both arrays and compare whether the element at array_sorted[i] and array_unsorted[i] are different.

You don't need to duplicate the array. Starting with the first element, compare to the next element in the array. If it's less than the current value, add one to the count and then look at the next value.