Heavily inspired by https://github.com/ole/SortedArray/

SortedArray.swift

struct SortedArray<Element, ComparableProperty: Comparable> {

    let propertyAccessor: (Element) -> ComparableProperty

    private var elements: [Element]

    public init(propertyAccessor: @escaping (Element) -> ComparableProperty) {
        self.elements = []
        self.propertyAccessor = propertyAccessor
    }

    public init<S: Sequence>(unsorted: S, propertyAccessor: @escaping (Element) -> ComparableProperty) where  S.Iterator.Element == Element {
        let sorted = unsorted.sorted(by: { propertyAccessor($0) < propertyAccessor($1) })
        self.elements = sorted
        self.propertyAccessor = propertyAccessor
    }

    @discardableResult
    public mutating func insert(_ newElement: Element) -> Index {
        let index = insertionIndex(for: newElement)
        elements.insert(newElement, at: index)
        return index
    }

    func insertionIndex(for element: Element) -> Index {
        var start = startIndex
        var end = endIndex
        let comparableProperty = propertyAccessor(element)
        while start < end {
            let middle = start / 2 + end / 2
            let currentMiddleProperty = propertyAccessor(elements[middle])
            if currentMiddleProperty == comparableProperty {
                return middle
            }
            if currentMiddleProperty < comparableProperty {
                start = middle + 1
            }
            if currentMiddleProperty > comparableProperty {
                end = middle
            }
        }
        return start
    }

    func index(of element: Element) -> Index? {
        var start = startIndex
        var end = endIndex
        let comparableProperty = propertyAccessor(element)
        while start < end {
            let middle = start / 2 + end / 2
            let currentMiddleProperty = propertyAccessor(elements[middle])
            if currentMiddleProperty == comparableProperty {
                return middle
            }
            if currentMiddleProperty < comparableProperty {
                start = middle + 1
            }
            if currentMiddleProperty > comparableProperty {
                end = middle
            }
        }
        return nil
    }

    public func contains(_ element: Element) -> Bool {
        return index(of: element) != nil
    }

    mutating func insert<S: Sequence>(contentsOf newElements: S) where S.Iterator.Element == Element {
        for element in newElements {
            insert(element)
        }
    }

}

extension SortedArray where Element: Comparable, Element == ComparableProperty {

    init() {
        self.init(propertyAccessor: { $0 })
    }

    init<S: Sequence>(unsorted: S) where S.Iterator.Element == Element {
        self.init(unsorted: unsorted, propertyAccessor: { $0 })
    }
}

extension SortedArray: RandomAccessCollection {
    public typealias Index = Int

    public var startIndex: Index { return elements.startIndex }

    public var endIndex: Index { return elements.endIndex }

    public func index(after i: Index) -> Index {
        return elements.index(after: i)
    }

    public func index(before i: Index) -> Index {
        return elements.index(before: i)
    }

    public subscript(position: Index) -> Element {
        return elements[position]
    }
}

extension SortedArray {

    @discardableResult
    public mutating func remove(at index: Int) -> Element {
        return elements.remove(at: index)
    }

    public mutating func removeSubrange(_ bounds: Range<Int>) {
        elements.removeSubrange(bounds)
    }

    public mutating func removeSubrange(_ bounds: ClosedRange<Int>) {
        elements.removeSubrange(bounds)
    }

    public mutating func removeSubrange(_ bounds: CountableRange<Int>) {
        elements.removeSubrange(bounds)
    }

    public mutating func removeSubrange(_ bounds: CountableClosedRange<Int>) {
        elements.removeSubrange(bounds)
    }

    public mutating func removeFirst(_ n: Int) {
        elements.removeFirst(n)
    }

    @discardableResult
    public mutating func removeFirst() -> Element {
        return elements.removeFirst()
    }

    @discardableResult
    public mutating func removeLast() -> Element {
        return elements.removeLast()
    }

    public mutating func removeLast(_ n: Int) {
        elements.removeLast(n)
    }

    public mutating func removeAll(keepingCapacity keepCapacity: Bool = true) {
        elements.removeAll(keepingCapacity: keepCapacity)
    }

    public mutating func remove(_ element: Element) {
        guard let index = index(of: element) else { return }
        elements.remove(at: index)
    }

    @warn_unqualified_access
    public func min() -> Element? {
        return first
    }

    @warn_unqualified_access
    public func max() -> Element? {
        return last
    }
}


extension SortedArray: Equatable where Element: Equatable {
    static func == (lhs: SortedArray<Element, ComparableProperty>, rhs: SortedArray<Element, ComparableProperty>) -> Bool {
        return lhs.elements.elementsEqual(rhs.elements)
    }
}

SortedArrayTests.swift

class SortedArrayTests: XCTestCase {

    func testBasic() {
        let sorted = SortedArray(unsorted: [1, 3, 2], propertyAccessor: { $0 })
        XCTAssertEqual(Array(sorted), [1, 2, 3])
    }

    func testConvenienceInitsUseLessThan() {
        let sorted = SortedArray(unsorted: ["a", "c", "b"])
        XCTAssertEqual(Array(sorted), ["a", "b", "c"])
    }

    func testInsertAtBeginningPreservesSortOrder() {
        var sorted = SortedArray(unsorted: 1...3)
        sorted.insert(0)
        XCTAssertEqual(Array(sorted), [0, 1, 2, 3])
    }


    func testInsertInMiddlePreservesSortOrder() {
        var sorted = SortedArray(unsorted: 1...5)
        sorted.insert(4)
        XCTAssertEqual(Array(sorted), [1, 2, 3, 4, 4, 5])
    }

    func testInsertAtEndPreservesSortOrder() {
        var sorted = SortedArray(unsorted: 1...3)
        sorted.insert(5)
        XCTAssertEqual(Array(sorted), [1, 2, 3, 5])
    }

    func testInsertAtBeginningReturnsInsertionIndex() {
        var sorted = SortedArray(unsorted: [1, 2, 3])
        let index = sorted.insert(0)
        XCTAssertEqual(index, 0)
    }

    func testInsertInMiddleReturnsInsertionIndex() {
        var sorted = SortedArray(unsorted: [1, 2, 3, 5])
        let index = sorted.insert(4)
        XCTAssertEqual(index, 3)
    }

    func testInsertAtEndReturnsInsertionIndex() {
        var sorted = SortedArray(unsorted: [1, 2, 3])
        let index = sorted.insert(100)
        XCTAssertEqual(index, 3)
    }

    func testInsertInEmptyArrayReturnsInsertionIndex() {
        var sorted = SortedArray<Int, Int>()
        let index = sorted.insert(10)
        XCTAssertEqual(index, 0)
    }

    func testInsertEqualElementReturnsCorrectInsertionIndex() {
        var sorted = SortedArray(unsorted: [3, 1, 0, 2, 1])
        let index = sorted.insert(1)
        XCTAssert(index == 1 || index == 2 || index == 3)
    }

    func testInsertContentsOfPreservesSortOrder() {
        var sorted = SortedArray(unsorted: [10, 9, 8])
        sorted.insert(contentsOf: (7...11).reversed())
        XCTAssertEqual(Array(sorted), [7, 8, 8, 9, 9, 10, 10, 11])
    }

    func testIndexOfFindsElementInMiddle() {
        let sorted = SortedArray(unsorted: ["a", "z", "r", "k"])
        let index = sorted.index(of: "k")
        XCTAssertEqual(index, 1)
    }

    func testIndexOfFindsFirstElement() {
        let sorted = SortedArray(unsorted: 1..<10)
        let index = sorted.index(of: 1)
        XCTAssertEqual(index, 0)
    }

    func testIndexOfFindsLastElement() {
        let sorted = SortedArray(unsorted: 1..<10)
        let index = sorted.index(of: 9)
        XCTAssertEqual(index, 8)
    }

    func testIndexOfReturnsNilWhenNotFound() {
        let sorted = SortedArray(unsorted: "Hello World")
        let index = sorted.index(of: "h")
        XCTAssertNil(index)
    }

    func testIndexOfReturnsNilForEmptyArray() {
        let sut = SortedArray<Int, Int>()
        let index = sut.index(of: 1)
        XCTAssertNil(index)
    }

    func testIndexOfCanDealWithSingleElementArray() {
        let sut = SortedArray(unsorted: [5])
        let index = sut.index(of: 5)
        XCTAssertEqual(index, 0)
    }

    func testsContains() {
        let sorted = SortedArray(unsorted: "Lorem ipsum")
        XCTAssertTrue(sorted.contains(" "))
        XCTAssertFalse(sorted.contains("a"))
    }

    func testMin() {
        let sorted = SortedArray(unsorted: -10...10)
        XCTAssertEqual(sorted.min(), -10)
    }

    func testMax() {
        let sorted = SortedArray(unsorted: -10...(-1))
        XCTAssertEqual(sorted.max(), -1)
    }

    func testRemoveAtIndex() {
        var sorted = SortedArray(unsorted: [3, 4, 2, 1])
        let removedElement = sorted.remove(at: 1)
        XCTAssertEqual(Array(sorted), [1, 3, 4])
        XCTAssertEqual(removedElement, 2)
    }

    func testRemoveSubrange() {
        var sorted = SortedArray(unsorted: ["a", "d", "c", "b"])
        sorted.removeSubrange(2..<4)
        XCTAssertEqual(Array(sorted), ["a", "b"])
    }

    func testRemoveFirst() {
        var sorted = SortedArray(unsorted: [3, 4, 2, 1])
        let removedElement = sorted.removeFirst()
        XCTAssertEqual(Array(sorted), [2, 3, 4])
        XCTAssertEqual(removedElement, 1)
    }

    func testRemoveFirstN() {
        var sorted = SortedArray(unsorted: [3, 4, 2, 1])
        sorted.removeFirst(2)
        XCTAssertEqual(Array(sorted), [3, 4])
    }

    func testRemoveLast() {
        var sorted = SortedArray(unsorted: [3, 4, 2, 1])
        let removedElement = sorted.removeLast()
        XCTAssertEqual(Array(sorted), [1, 2, 3])
        XCTAssertEqual(removedElement, 4)
    }

    func testRemoveLastN() {
        var sorted = SortedArray(unsorted: [3, 4, 2, 1])
        sorted.removeLast(2)
        XCTAssertEqual(Array(sorted), [1, 2])
    }

    func testRemoveAll() {
        var sorted = SortedArray(unsorted: ["a", "d", "c", "b"])
        sorted.removeAll()
        XCTAssertEqual(Array(sorted), [])
    }

    func testRemoveElementAtBeginningPreservesSortOrder() {
        var sorted = SortedArray(unsorted: 1...3)
        sorted.remove(1)
        XCTAssertEqual(Array(sorted), [2, 3])
    }

    func testRemoveElementInMiddlePreservesSortOrder() {
        var sorted = SortedArray(unsorted: 1...5)
        sorted.remove(4)
        XCTAssertEqual(Array(sorted), [1, 2, 3, 5])
    }

    func testRemoveElementAtEndPreservesSortOrder() {
        var sorted = SortedArray(unsorted: 1...3)
        sorted.remove(3)
        XCTAssertEqual(Array(sorted), [1, 2])
    }

    func testImplementsEqual() {
        let sorted = SortedArray(unsorted: [3, 2, 1])
        XCTAssertTrue(sorted == SortedArray(unsorted: 1...3))
    }

    func testImplementsNotEqual() {
        let sorted = SortedArray(unsorted: 1...3)
        XCTAssertTrue(sorted != SortedArray(unsorted: 1...4))
    }

}