Bubble sort's true complexity is O(n+d) where d is the number of inversions in the array. So if an array is almost sorted better to use bubble sort.