title: Which general purpose sorting algorithm does Swift use? It does not perform well on sorted data
body: <p>I have been picking and probing at Swift standard libraries <code>sort()</code> function for its <code>Array</code> type. To my surprise I have noticed it performs poorly on already-sorted data. </p>
  
  <p>Sorting an array of <code>Int</code> which is shuffled seems to be 5x faster than sorting that very same array when it is already sorted. Sorting an array of shuffled objects is about 4x faster than sorting the very same one already in sorted order (sorting object array vs <code>Int</code> array use different algorithms I am sure so I sorted both to eliminate bias). </p>
  
  <p>These are the results:</p>
  
  <pre><code>Shuffled Int array sort time: 1.3961209654808
  Shuffled ColorObject array sort time: 3.14633798599243
  NOnshuffled Int array sort time: 7.34714204072952
  NOnshuffled ColorObject array sort time: 10.9310839772224
  </code></pre>
  
  <p>For reference below is my code:</p>
  
  <pre><code>class ElapsedTimer {
  
      let startTime: CFAbsoluteTime
      var endTime: CFAbsoluteTime?
  
      init() {
          startTime = CFAbsoluteTimeGetCurrent()
      }
  
      func stop() -&gt; CFAbsoluteTime {
          endTime = CFAbsoluteTimeGetCurrent()
          return duration!
      }
  
      var duration: CFAbsoluteTime? {
          if let endTime = endTime {
              return endTime - startTime
          } else {
              return nil
          }
      }
  }
  
  public class CountedColor {
      public private(set) var count: Int
      public private(set) var color: UIColor
  
      public init(color: UIColor, colorCount: Int) {
          self.count = colorCount
          self.color = color
      }
  }
  
  var distributedIntArray = [Int]()
  
  for value in 1..&lt;1000000 {
      distributedIntArray.append(value)
  }
  
  var distributedCountedColorArray = distributedIntArray.map{ CountedColor(color: UIColor.white, colorCount: $0) }
  
  distributedCountedColorArray.shuffle()
  distributedIntArray.shuffle()
  
  var timer = ElapsedTimer()
  distributedIntArray.sort()
  print("Shuffled Int array sort time: \(timer.stop())")
  timer = ElapsedTimer()
  
  distributedCountedColorArray.sort{ return $0.count &lt; $1.count }
  print("Shuffled Color array sort time: \(timer.stop())")
  timer = ElapsedTimer()
  
  distributedIntArray.sort()
  print("NOnshuffled Int array sort time: \(timer.stop())")
  timer = ElapsedTimer()
  
  distributedCountedColorArray.sort{ return $0.count &lt; $1.count }
  print("Non shuffled Color array sort time: \(timer.stop())")
  </code></pre>
  
  <p>My array <code>shuffle()</code> method was pulled from <a href="https://stackoverflow.com/questions/37843647/shuffle-array-swift-3/37843901">this post</a>. My <code>ElapsedTimer</code> simply wraps and uses <code>CACurrentMediaTime()</code> functions.</p>
  
  <p>My question is why am I seeing this behavior? Especially when I am sorting the object array which should surely be using a general purpose sort. What kind of general purpose sorting algorithm is swift using? It surely can’t be one where the worst case and average case are the same like mergeSort.</p>