How do I insert an element at the correct position into a sorted array in Swift?

Here is a possible implementation in Swift using binary search (from http://rosettacode.org/wiki/Binary_search#Swift with slight modifications):

extension Array {
    func insertionIndexOf(_ elem: Element, isOrderedBefore: (Element, Element) -> Bool) -> Int {
        var lo = 0
        var hi = self.count - 1
        while lo <= hi {
            let mid = (lo + hi)/2
            if isOrderedBefore(self[mid], elem) {
                lo = mid + 1
            } else if isOrderedBefore(elem, self[mid]) {
                hi = mid - 1
            } else {
                return mid // found at position mid
            }
        }
        return lo // not found, would be inserted at position lo
    }
}

As with indexOfObject:inSortedRange:options:usingComparator: it is assumed that the array is sorted with respect to the comparator. It returns either (any) index of the element if the element is already present in the array, or the index where it can be inserted while preserving the order. This corresponds to the NSBinarySearchingInsertionIndex of the NSArray method.

Usage:

let newElement = "c"
let index = myArray.insertionIndexOf(newElement) { $0 < $1 } // Or: myArray.indexOf(c, <)
myArray.insert(newElement, at: index)

In swift 3 you can use index(where:):

var myArray = ["a", "b", "d", "e"]
let newElement = "c"
if let index = myArray.index(where: { $0 > newElement }) {
    myArray.insert(newElement, at: index)
}

Note that in this case you need to reverse the condition inside the closure (i.e. > instead of < for increasing elements in array), because the index you are interested in is the first element that does NOT match the predicate. Also, this method will return nil if the newly inserted element is going to be the last in the array (newElement = "z" in the example above.

For convenience, this can be wrapped to a separate function that will handle all these issues:

extension Collection {
    func insertionIndex(of element: Self.Iterator.Element,
                        using areInIncreasingOrder: (Self.Iterator.Element, Self.Iterator.Element) -> Bool) -> Index {
        return index(where: { !areInIncreasingOrder($0, element) }) ?? endIndex
    }
}

Usage:

var myArray = ["a", "b", "d", "e"]
let newElement = "c"
let index = myArray.insertionIndex(of: newElement, using: <)
myArray.insert(newElement, at: index)

According to WWDC 2018 Session 406: Swift Generics (Expanded) the binary search can be performed in a more efficient and even more generic way by slicing the collection object.

There are two considerable benefits of Slice:

1. A slice is always a subset of the original object without allocating additional memory.
2. All indices of the slice refer to the original object.
   For example if you slice an array of 5 objects let slice = array[2..<4] then slice.startIndex is 2 not 0.

RandomAccessCollection is a protocol (inherited from BidirectionalCollection) which a variety of structs / classes conform to

extension RandomAccessCollection where Element : Comparable {
    func insertionIndex(of value: Element) -> Index {
        var slice : SubSequence = self[...]

        while !slice.isEmpty {
            let middle = slice.index(slice.startIndex, offsetBy: slice.count / 2)
            if value < slice[middle] {
                slice = slice[..<middle]
            } else {
                slice = slice[index(after: middle)...]
            }
        }
        return slice.startIndex
    }
}

Example:

let array = [1, 2, 4, 7, 8]
let index = array.insertionIndex(of: 6) // 3

You can extend the function to check against a predicate closure instead of a single value

extension RandomAccessCollection { // the predicate version is not required to conform to Comparable
    func insertionIndex(for predicate: (Element) -> Bool) -> Index {
        var slice : SubSequence = self[...]

        while !slice.isEmpty {
            let middle = slice.index(slice.startIndex, offsetBy: slice.count / 2)
            if predicate(slice[middle]) {
                slice = slice[index(after: middle)...]
            } else {
                slice = slice[..<middle]
            }
        }
        return slice.startIndex
    }
}

Example:

struct Person { let name : String }

let array = [Person(name: "Adam"), Person(name: "Cynthia"), Person(name: "Nancy"), Person(name: "Tom")]
let index = array.insertionIndex{ $0.name < "Bruce" } // 1