Insertion Sort in Swift implemented as an extension on `MutableCollectionType`

InsertionSort.swift

// Swift 2.1

extension MutableCollectionType where Self.Generator.Element : Comparable {
    
    /// Return a new sorted collection of the elements in `source`
    /// using [Insertion Sort](https://en.wikipedia.org/wiki/Insertion_sort).
    ///
    /// Complexity O(n^2).
    @warn_unused_result(mutable_variant="insertionSortInPlace")
    public func insertionSort() -> Self {
    
        var output = self
        
        for primaryIndex in output.indices {
            
            for secondaryIndex in (startIndex.successor() ... primaryIndex).reverse() {
                
                if output[secondaryIndex] < output[secondaryIndex.advancedBy(-1)] {
                    swap(&output[secondaryIndex], &output[secondaryIndex.advancedBy(-1)])
                }
                
            }
            
        }
        
        return output
    
    }
    
    /// Sort `self` in-place using [Insertion Sort](https://en.wikipedia.org/wiki/Insertion_sort).
    ///
    /// Complexity O(n^2).
    public mutating func insertionSortInPlace() {
        
        for primaryIndex in self.indices {
            
            for secondaryIndex in (startIndex.successor() ... primaryIndex).reverse() {
            
                if self[secondaryIndex] < self[secondaryIndex.advancedBy(-1)] {
                    swap(&self[secondaryIndex], &self[secondaryIndex.advancedBy(-1)])
                }
                
            }
            
        }
    }
}

func testInsertionSort() {
    
    var integers = [2, 10, 5, 3, 8, 4, 7, 9, 6, 1]
    
    // Test that `insertionSort()` returns a sorted array.
    assert(integers.insertionSort() == [1, 2, 3, 4, 5, 6, 7, 8, 9, 10])
    
    // Test that `integers` has not changed.
    assert(integers == [2, 10, 5, 3, 8, 4, 7, 9, 6, 1])
    
    // mutate `integers` to become sorted.
    integers.insertionSortInPlace()

    // Test that `integers` is now sorted.
    assert(integers == [1, 2, 3, 4, 5, 6, 7, 8, 9, 10])
    
    print("insertion sort tests pass")
    
}