Sort a collection using Shell's method. Implemented in Swift as an extension on `MutableCollectionType`.

ShellSort.swift

// Swift 2.1

extension MutableCollectionType where Self.Generator.Element : Comparable, Self.Index == Int {
    
    /// Return a new sorted collection of the elements in `source`
    /// using [Shell Sort](https://en.wikipedia.org/wiki/Shellsort).
    ///
    /// Complexity O(n^(3/2)).
    @warn_unused_result(mutable_variant="shellSortInPlace")

    func shellSort() -> Self {
        
        var output = self
        var increment = 1
        
        while increment < output.endIndex / 3 {
            increment = 3 * increment + 1
        }
        
        while increment >= 1 {
            
            for (var index, element) in output.enumerate() {
                while index >= increment && output[index - increment] > element {
                    output[index] = output[index - increment]
                    index -= increment
                }
                output[index] = element
            }
            
            increment /= 3
        }
        
        return output
        
    }

    /// Sort `self` in-place using [Shell Sort](https://en.wikipedia.org/wiki/Shellsort).
    ///
    /// Complexity O(n^(3/2)).
    mutating func shellSortInPlace() {
        
        var increment = 1
        
        while increment < self.endIndex / 3 {
            increment = 3 * increment + 1
        }
        
        while increment >= 1 {
            
            for (var index, element) in self.enumerate() {
                while index >= increment && self[index - increment] > element {
                    self[index] = self[index - increment]
                    index -= increment
                }
                self[index] = element
            }
            
            increment /= 3
        }
    }
}

func testShellSort() {
    
    var integers = [2, 10, 5, 3, 8, 4, 7, 9, 6, 1]
    
    // test that `shellSort` returns a sorted array.
    assert(integers.shellSort() == [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.shellSortInPlace()
 
    // Test that `integers` is now sorted.
    assert(integers == [1, 2, 3, 4, 5, 6, 7, 8, 9, 10])
    
    print("Shell sort tests passed")
}