CODEWITHSUNDEEP
sortinginsertion-sort
João Pires
João Pires

Reputation: 1017

Sorted array except for last element

Given an already sorted array of n distinct elements where only the last element is out of order, would insertion sort be the fastest algorithm to be used here?

Ex: [1, 3, 5, 6, 7, 9, 2]

Upvotes: 1

Views: 351

Answers (1)

Sankalp Mukim
Sankalp Mukim

Reputation: 80

If it was an array, yes, insertion sort.

Worst case complexity: O(n)

Worst case scenario: Unsorted element is the smallest element.

If it was a linked list of any kind where the cost of insertion is constant time, then a binary search would be the fastest most efficient way.

Worst case complexity: O(log(n))

Upvotes: 1

Related Questions