-
Notifications
You must be signed in to change notification settings - Fork 3
/
Copy pathintrosort-timsort-swifts-sorting-algorithm.html
460 lines (412 loc) · 26.8 KB
/
introsort-timsort-swifts-sorting-algorithm.html
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
<!DOCTYPE html>
<html lang="en">
<head>
<script src="https://use.fontawesome.com/afd448ce82.js"></script>
<!-- Meta Tag -->
<meta charset="UTF-8">
<meta name="viewport" content="width=device-width, initial-scale=1.0">
<meta http-equiv="X-UA-Compatible" content="IE=edge">
<!-- SEO -->
<meta name="author" content="Bruno Rocha">
<meta name="keywords" content="Software, Engineering, Blog, Posts, iOS, Xcode, Swift, Articles, Tutorials, OBJ-C, Objective-C, Apple">
<meta name="description" content="Have you ever asked yourself which algorithm is used by Swift's sorting method? There are many sorting algorithms out there, and chances are that you'll rarely have to use something other than the language's builtin sort() method. However, knowing the properties of the sorting algorithm built into your language is important if you want to prevent unwanted behaviors and nasty edge cases.">
<meta name="title" content="Timsort and Introsort: Swift's Sorting Algorithms">
<meta name="url" content="https://swiftrocks.com/introsort-timsort-swifts-sorting-algorithm">
<meta name="image" content="https://swiftrocks.com/images/thumbs/thumb.jpg?4">
<meta name="copyright" content="Bruno Rocha">
<meta name="robots" content="index,follow">
<meta property="og:title" content="Timsort and Introsort: Swift's Sorting Algorithms"/>
<meta property="og:image" content="https://swiftrocks.com/images/thumbs/thumb.jpg?4"/>
<meta property="og:description" content="Have you ever asked yourself which algorithm is used by Swift's sorting method? There are many sorting algorithms out there, and chances are that you'll rarely have to use something other than the language's builtin sort() method. However, knowing the properties of the sorting algorithm built into your language is important if you want to prevent unwanted behaviors and nasty edge cases."/>
<meta property="og:type" content="website"/>
<meta property="og:url" content="https://swiftrocks.com/introsort-timsort-swifts-sorting-algorithm"/>
<meta name="twitter:card" content="summary_large_image"/>
<meta name="twitter:image" content="https://swiftrocks.com/images/thumbs/thumb.jpg?4"/>
<meta name="twitter:image:alt" content="Page Thumbnail"/>
<meta name="twitter:title" content="Timsort and Introsort: Swift's Sorting Algorithms"/>
<meta name="twitter:description" content="Have you ever asked yourself which algorithm is used by Swift's sorting method? There are many sorting algorithms out there, and chances are that you'll rarely have to use something other than the language's builtin sort() method. However, knowing the properties of the sorting algorithm built into your language is important if you want to prevent unwanted behaviors and nasty edge cases."/>
<meta name="twitter:site" content="@rockbruno_"/>
<!-- Favicon -->
<link rel="icon" type="image/png" href="images/favicon/iconsmall2.png" sizes="32x32" />
<link rel="apple-touch-icon" href="images/favicon/iconsmall2.png">
<link rel="preconnect" href="https://fonts.googleapis.com">
<link rel="preconnect" href="https://fonts.gstatic.com" crossorigin>
<link href="https://fonts.googleapis.com/css2?family=Source+Sans+3:ital,wght@0,200..900;1,200..900&display=swap" rel="stylesheet">
<link rel="canonical" href="https://swiftrocks.com/introsort-timsort-swifts-sorting-algorithm"/>
<!-- Bootstrap CSS Plugins -->
<link rel="stylesheet" type="text/css" href="css/bootstrap.css">
<!-- Prism CSS Stylesheet -->
<link rel="stylesheet" type="text/css" href="css/prism4.css">
<!-- Main CSS Stylesheet -->
<link rel="stylesheet" type="text/css" href="css/style48.css">
<link rel="stylesheet" type="text/css" href="css/sponsor4.css">
<!-- HTML5 shiv and Respond.js support IE8 or Older for HTML5 elements and media queries -->
<!--[if lt IE 9]>
<script src="https://oss.maxcdn.com/html5shiv/3.7.3/html5shiv.min.js"></script>
<script src="https://oss.maxcdn.com/respond/1.4.2/respond.min.js"></script>
<![endif]-->
<script type="application/ld+json">
{
"@context": "https://schema.org",
"@type": "BlogPosting",
"mainEntityOfPage": {
"@type": "WebPage",
"@id": "https://swiftrocks.com/introsort-timsort-swifts-sorting-algorithm"
},
"image": [
"https://swiftrocks.com/images/thumbs/thumb.jpg"
],
"datePublished": "2019-09-04T18:00:00+00:00",
"dateModified": "2020-04-12T14:00:00+02:00",
"author": {
"@type": "Person",
"name": "Bruno Rocha"
},
"publisher": {
"@type": "Organization",
"name": "SwiftRocks",
"logo": {
"@type": "ImageObject",
"url": "https://swiftrocks.com/images/thumbs/thumb.jpg"
}
},
"headline": "Timsort and Introsort: Swift's Sorting Algorithms",
"abstract": "Have you ever asked yourself which algorithm is used by Swift's sorting method? There are many sorting algorithms out there, and chances are that you'll rarely have to use something other than the language's builtin sort() method. However, knowing the properties of the sorting algorithm built into your language is important if you want to prevent unwanted behaviors and nasty edge cases."
}
</script>
</head>
<body>
<div id="main">
<!-- Blog Header -->
<!-- Blog Post (Right Sidebar) Start -->
<div class="container">
<div class="col-xs-12">
<div class="page-body">
<div class="row">
<div><a href="https://swiftrocks.com">
<img id="logo" class="logo" alt="SwiftRocks" src="images/bg/logo2light.png">
</a>
<div class="menu-large">
<div class="menu-arrow-right"></div>
<div class="menu-header menu-header-large">
<div class="menu-item">
<a href="blog">blog</a>
</div>
<div class="menu-item">
<a href="about">about</a>
</div>
<div class="menu-item">
<a href="talks">talks</a>
</div>
<div class="menu-item">
<a href="projects">projects</a>
</div>
<div class="menu-item">
<a href="software-engineering-book-recommendations">book recs</a>
</div>
<div class="menu-item">
<a href="games">game recs</a>
</div>
<div class="menu-arrow-right-2"></div>
</div>
</div>
<div class="menu-small">
<div class="menu-arrow-right"></div>
<div class="menu-header menu-header-small-1">
<div class="menu-item">
<a href="blog">blog</a>
</div>
<div class="menu-item">
<a href="about">about</a>
</div>
<div class="menu-item">
<a href="talks">talks</a>
</div>
<div class="menu-item">
<a href="projects">projects</a>
</div>
<div class="menu-arrow-right-2"></div>
</div>
<div class="menu-arrow-right"></div>
<div class="menu-header menu-header-small-2">
<div class="menu-item">
<a href="software-engineering-book-recommendations">book recs</a>
</div>
<div class="menu-item">
<a href="games">game recs</a>
</div>
<div class="menu-arrow-right-2"></div>
</div>
</div>
</div>
<div class="content-page" id="WRITEIT_DYNAMIC_CONTENT">
<!--WRITEIT_POST_NAME=Timsort and Introsort: Swift's Sorting Algorithms-->
<!--WRITEIT_POST_HTML_NAME=introsort-timsort-swifts-sorting-algorithm-->
<!--WRITEIT_POST_SITEMAP_DATE_LAST_MOD=2020-04-12T14:00:00+02:00-->
<!--WRITEIT_POST_SITEMAP_DATE=2019-09-04T18:00:00+00:00-->
<!--Add here the additional properties that you want each page to possess.-->
<!--These properties can be used to change content in the template page or in the page itself as shown here.-->
<!--Properties must start with 'WRITEIT_POST'.-->
<!--Writeit provides and injects WRITEIT_POST_NAME and WRITEIT_POST_HTML_NAME by default.-->
<!--WRITEIT_POST_SHORT_DESCRIPTION=Have you ever asked yourself which algorithm is used by Swift's sorting method? There are many sorting algorithms out there, and chances are that you'll rarely have to use something other than the language's builtin sort() method. However, knowing the properties of the sorting algorithm built into your language is important if you want to prevent unwanted behaviors and nasty edge cases.-->
<title>Timsort and Introsort: Swift's Sorting Algorithms</title>
<div class="blog-post">
<div class="post-title-index">
<h1>Timsort and Introsort: Swift's Sorting Algorithms</h1>
</div>
<div class="post-info">
<div class="post-info-text">
Published on 04 Sep 2019
</div>
</div>
<p>Have you ever asked yourself which algorithm is used by Swift's sorting method? There are many sorting algorithms out there, and chances are that you'll rarely have to use something other than the language's builtin <code>sort()</code> method. However, knowing the properties of the sorting algorithm built into your language is important if you want to prevent unwanted behaviors and nasty edge cases.</p>
<div class="sponsor-article-ad-auto hidden"></div>
<p>When analyzing sorting algorithms, you'll want to search for two properties:</p>
<h2>1 - Sorting Stability</h2>
<p>The <b>stability</b> of a sorting algorithm represents the ability of the algorithm to <b>maintain the original order of equal elements after sorting</b>. An <b>unstable</b> sorting algorithm has no guarantees that the order of equal elements in the unsorted array will stay the same after sorting, while a <b>stable</b> one guarantees that they will stay the same.</p>
<p>This might sound weird, after all, if the elements are the same, why should I care about their overall order? This can be true if you're sorting elements by value, but when sorting elements by some arbitrary <b>priority</b>, using unstable algorithms can give you undesired results.</p>
<p>Let's assume that we're building a music player, and our current task is to sort songs based on their popularity:</p>
<pre><code>struct Music: Comparable, Equatable, CustomStringConvertible {
let name: String
let popularityValue: Int
static func < (lhs: Music, rhs: Music) -> Bool {
return lhs.popularityValue < rhs.popularityValue
}
var description: String {
return name
}
}
var songs: [Music] = [
Music(name: "I'm that swifty", popularityValue: 3),
Music(name: "Swift boi", popularityValue: 5),
Music(name: "Swift That Walk", popularityValue: 1),
Music(name: "Too Swift", popularityValue: 5),
]</code></pre>
<p>If we sort <code>songs</code> using Quicksort, we'll get the following result:</p>
<pre><code>extension Array where Element: Equatable & Comparable {
func quicksort(comparison: ((Element, Element) -> Bool)) -> [Element] {
var copy = self
copy.quick(0, count - 1, comparison: comparison)
return copy
}
mutating private func quick(_ i: Int, _ j: Int, comparison: ((Element, Element) -> Bool)) {
guard i < j else {
return
}
let pivot = partition(i, j, comparison: comparison)
quick(i, pivot - 1, comparison: comparison)
quick(pivot + 1, j, comparison: comparison)
}
mutating private func partition(_ i: Int, _ j: Int, comparison: ((Element, Element) -> Bool)) -> Int {
let pivotElement = self[j]
var indexToAdd = i - 1
for k in i..<j {
if comparison(self[k], pivotElement) {
indexToAdd += 1
swapAt(indexToAdd, k)
}
}
swapAt(indexToAdd + 1, j)
return indexToAdd + 1
}
}
songs = songs.quicksort {
$0.popularityValue > $1.popularityValue
}
print(songs)</code></pre>
<pre><code>// [Too Swift, Swift boi, I'm that swifty, Swift That Walk]</code></pre>
<p>Although <code>"Swift boi"</code> was placed before <code>"Too Swift"</code> in the original array, Quicksort changed their positions!</p>
<p>That's not too bad though as we never actually used the unsorted version of the array. However, consider what happens if we re-sort the array multiple times:</p>
<pre><code>songs = songs.quicksort {
$0.popularityValue > $1.popularityValue
}
print(songs)
songs = songs.quicksort {
$0.popularityValue > $1.popularityValue
}
print(songs)
songs = songs.quicksort {
$0.popularityValue > $1.popularityValue
}
print(songs)
songs = songs.quicksort {
$0.popularityValue > $1.popularityValue
}
print(songs)
songs = songs.quicksort {
$0.popularityValue > $1.popularityValue
}
print(songs)</code></pre>
<pre><code>// [Too Swift, Swift boi, I'm that swifty, Swift That Walk]
// [Swift boi, Too Swift, I'm that swifty, Swift That Walk]
// [Too Swift, Swift boi, I'm that swifty, Swift That Walk]
// [Swift boi, Too Swift, I'm that swifty, Swift That Walk]
// [Too Swift, Swift boi, I'm that swifty, Swift That Walk]</code></pre>
<p>Their relative order keeps changing!</p>
<p>The reason is because Quicksort is an <b>unstable</b> sorting algorithm. If for some reason we needed to continuously update this list in the UI, the user would see songs changing positions in the ranking even though they have the same priority. That's not very good.</p>
<p>To keep their order, we need to use a <b>stable</b> algorithm like <b>Mergesort</b>.</p>
<pre><code>extension Array where Element: Equatable & Comparable {
func mergesort(comparison: ((Element, Element) -> Bool)) -> [Element] {
return merge(0, count - 1, comparison: comparison)
}
private func merge(_ i: Int, _ j: Int, comparison: ((Element, Element) -> Bool)) -> [Element] {
guard i <= j else {
return []
}
guard i != j else {
return [self[i]]
}
let half = i + (j - i) / 2
let left = merge(i, half, comparison: comparison)
let right = merge(half + 1, j, comparison: comparison)
var i1 = 0
var i2 = 0
var new = [Element]()
new.reserveCapacity(left.count + right.count)
while i1 < left.count && i2 < right.count {
if comparison(right[i2], left[i1]) {
new.append(right[i2])
i2 += 1
} else {
new.append(left[i1])
i1 += 1
}
}
while i1 < left.count {
new.append(left[i1])
i1 += 1
}
while i2 < right.count {
new.append(right[i2])
i2 += 1
}
return new
}
}</code></pre>
<pre><code>// [Swift boi, Too Swift, I'm that swifty, Swift That Walk]
// [Swift boi, Too Swift, I'm that swifty, Swift That Walk]
// [Swift boi, Too Swift, I'm that swifty, Swift That Walk]
// [Swift boi, Too Swift, I'm that swifty, Swift That Walk]
// [Swift boi, Too Swift, I'm that swifty, Swift That Walk]</code></pre>
<h2>2 - Time/Space Complexity</h2>
<p>The second important thing to be aware of is how much additional memory the algorithm takes to run and what are best/worst cases for the algorithm.</p>
<p>My favorite example of this is <b>Counting Sort</b>: where an array is sorted by simply counting the occurrences of each element number of elements and then laying them out in order. If the difference between each value is small, say <code>[3,1,4,2,5]</code>, this algorithm can sort arrays in runtimes very close to <b>O(n)</b> -- but if the difference is big, like <code>[1,1000000000]</code>, Counting Sort will take an enormous amount of time to run even if the array is small.</p>
<p>Likewise, the famous Quick Sort is highly regarded for being a fast and in-place O(n log n) algorithm in average, but it has a terrible worst case of O(n2) if the pivot is always the highest/smallest element in the partition. If you're dealing with large amounts of data or a constrained environment, there will be a specific sorting algorithm that best fits your needs.</p>
<h2>Pre-Swift 5 Algorithm: Introsort</h2>
<p>Before Swift 5, Swift's sorting algorithm was a hybrid algorithm called <b>Introsort</b>, which mixes the strengths of <code>Quicksort</code>, <code>Heapsort</code> and <code>Insertion Sort</code> into a single algorithm to guarantee a worse case of O(n log n).</p>
<p>The idea behind Introsort is straightforward: First, if you have <b>less than 20 elements</b> in the partition being sorted, Insertion Sort is used. Although this algorithm has a worst case of O(n2), it also has a best case of O(n). Compared to the general O(n log n) algorithms, Insertion Sort will always perform better in small inputs.</p>
<p>If the array is not small, Quicksort will be used. This will bring our best case to O(n log n), but also maintain the worst case of O(n2). However, Introsort can avoid it -- if the recursion tree for Quicksort gets too deep, the partition switches to Heapsort. In this case, "too deep" is considered as <code>2 * floor(log2(array.count))</code>.</p>
<pre><code>internal mutating func _introSortImpl(within range: Range<Index>,
by areInIncreasingOrder: (Element, Element) throws -> Bool,
depthLimit: Int) rethrows {
// Insertion sort is better at handling smaller regions.
if distance(from: range.lowerBound, to: range.upperBound) < 20 {
try _insertionSort(within: range, by: areInIncreasingOrder)
} else if depthLimit == 0 {
try _heapSort(within: range, by: areInIncreasingOrder)
} else {
// Partition and sort.
// We don't check the depthLimit variable for underflow because this
// variable is always greater than zero (see check above).
let partIdx = try _partition(within: range, by: areInIncreasingOrder)
try _introSortImpl(
within: range.lowerBound..<partIdx,
by: areInIncreasingOrder,
depthLimit: depthLimit &- 1)
try _introSortImpl(
within: partIdx..<range.upperBound,
by: areInIncreasingOrder,
depthLimit: depthLimit &- 1)
}
}</code></pre>
<p>Introsort greedily attempts to pick the best algorithm for the given situation, backing up to a different option when the previous choice goes wrong. It has a best case of O(n) and worst case of O(n log n), making it a decent one-size-fits-all algorithm.</p>
<p>In terms of memory usage, it will perform slightly worse than the usual sorting algorithm. Although the three algorithms can sort inplace, Introsort's implementation in Swift was recursive. Since Swift doesn't guarantee that tail recursion calls will be optimized, running the builtin <code>sort()</code> pre-Swift 5 was not the best option if keeping memory usage low was important.</p>
<p>The biggest thing to note is that Introsort was <b>unstable</b>. Although Insertion Sort is stable, the default implementation of Quicksort and Heapsort are not. If the order of equal elements was important, using <code>sort()</code> pre-Swift 5 was also not a good idea.</p>
<h2>After Swift 5 - Timsort</h2>
<p>Multiple threads surfaced between 2015 and 2018 about adding a stable sorting algorithm to Swift that didn't rely on recursion, but promising discussions first showed up only in the beginning of 2018. In October 2018, <a href="https://github.com/apple/swift/pull/19717">a pull request was finally merged</a> to change Introsort to a modified version of <b>Timsort.</b></p>
<p>Timsort is a hybrid algorithm like Introsort, but with different approaches. It works by dividing an array into smaller sections, sorting these smaller sections with Insertion Sort, and then merging these sections together with Merge Sort. Because both Insertion Sort and Mergesort are stable, Timsort is <b>stable</b>, and while it also has a worst case of O(n log n) and non-constant space complexity, it tends to be considerably quicker than the more naive algorithms in real world scenarios. The reason why Timsort can be so fast is that although the description sounds simple enough, in reality each of these steps are highly tuned for efficiency.</p>
<h3>Finding the next "run" (Partitioning)</h3>
<p>Instead of dividing everything first and merging as the last step like Mergesort, Timsort scans the array once and progressively merge these regions (called "runs") as they are found.</p>
<p>The beauty is that unlike Mergesort, a run isn't simply the array divided by half. Timsort abuses the fact that every array that you want to sort is likely to have a few contiguous subsequences that are <b>almost or already sorted</b>, which happens to be Insertion Sort's best case. To find the next run, Timsort will advance a pointer until the current sequence stops being an ascending/descending pattern:</p>
<pre><code>[1, 2, 3, 1, 9, 6]
i j</code></pre>
<p><i>Note: This example is just for visual purposes -- because the array here is small, Timsort would just Insertion Sort it right away.</i></p>
<p>The range from i to j defines our first run <b>run</b>, but the optimizations don't stop here.</p>
<p>First: If the sequence is descending, we can already sort it in linear time by reversing the elements.</p>
<p>Second: To increase the speed of Insertion Sort and to balance the amount of merge operations that will be done later, Timsort defines that every run should have a <b>minimum size</b> of a power of two between 16 and 128, or at least something very close to it. If the run that we found has a size smaller than the minimum run size, then the current run's range is expanded and sorted with Insertion Sort.</p>
<pre><code>// Find the next consecutive run, reversing it if necessary.
var (end, descending) = try _findNextRun(in: self, from: start, by: areInIncreasingOrder)
if descending {
_reverse(within: start..<end)
}
// If the current run is shorter than the minimum length, use the
// insertion sort to extend it.
if end < endIndex && end - start < minimumRunLength {
let newEnd = Swift.min(endIndex, start + minimumRunLength)
try _insertionSort(within: start..<newEnd, sortedEnd: end, by: areInIncreasingOrder)
end = newEnd
}</code></pre>
<p>For the actual size, Swift specifically will pick a value between 32 and 64 that varies according to the size of the array. Finally, after a run is found, it's added to a stack containing all the other previous runs that we've found.</p>
<h3>Merging runs</h3>
<p>Every time a run is found, Timsort will attempt to collapse the top three runs of the stack into a single one by merging them together until the following conditions are satisfied:</p>
<pre><code>runs.count < 3 || runs[runs.count - 2].size > (runs[runs.count - 1].size + runs.last!.count)
&&
runs.count < 2 || runs[runs.count - 1].size > runs.last!.size</code></pre>
<p>This is done to reduce the amount of runs we have to remember, but mainly to balance the overall size of the runs as having them close together is beneficial for Timsort's merging phase.</p>
<p>At first glance Timsort's merging phase works just like Mergesort: we compare a pair of elements from each array, picking the smallest one and moving it to its proper position in the final array.</p>
<p>However, Timsort beautifully empowers the fact that if one specific array keeps "winning" the comparison, then it's likely to keep doing so. If this happens, instead of continuing to compare elements, we can simply binary search for the correct position of the element from the "losing" array in the "winning" one, moving all elements before it to the final array. This is called <b>galloping</b> and it saves us a lot of time by letting us skip comparing an entire chunk of the winning array.</p>
<p>The galloping process can be aborted if the binary search process "loses" to the regular comparison process. <a href="https://bugs.python.org/file4451/timsort.txt">You can see all the optimizations that are done in the Timsort description.</a> Finally, after all runs were found, the remaining runs in the stack are progressively merged together until the entire array is sorted.</p>
<p>The major differences in Swift is that the compiler's implementation of Timsort doesn't use galloping, and it attempts to collapse runs based on the last four runs instead of the last three. Still, it outperforms Introsort in pretty much every scenario.</p>
<h2>Conclusion</h2>
<div class="sponsor-article-ad-auto hidden"></div>
<p>Timsort is one of the fastest sorting algorithms for real world problems. Knowing what algorithm your language uses can help you optimize your code by making better decisions based on what data you're handling.</p>
<p>Follow me on my Twitter (<a href="https://twitter.com/rockbruno_">@rockbruno_</a>), and let me know of any suggestions and corrections you want to share.</p>
<h2>References and Good reads</h2>
<a href="https://forums.swift.org/t/starter-proposal-add-stable-sort-to-stdlib/9309">Stable Sort Proposal</a>
<br>
<a href="https://github.com/apple/swift/pull/19717">Stable Sort PR</a>
<br>
<a href="https://en.wikipedia.org/wiki/Introsort">Introsort</a>
<br>
<a href="https://svn.python.org/projects/python/trunk/Objects/listsort.txt">Timsort</a>
<br>
<a href="https://en.wikipedia.org/wiki/Timsort">Timsort (Wiki)</a>
</div></div>
<div class="blog-post footer-main">
<div class="footer-logos">
<a href="https://swiftrocks.com/rss.xml"><i class="fa fa-rss"></i></a>
<a href="https://twitter.com/rockbruno_"><i class="fa fa-twitter"></i></a>
<a href="https://github.com/rockbruno"><i class="fa fa-github"></i></a>
</div>
<div class="footer-text">
© 2025 Bruno Rocha
</div>
<div class="footer-text">
<p><a href="https://swiftrocks.com">Home</a> / <a href="blog">See all posts</a></p>
</div>
</div>
</div>
</div>
</div>
</div>
</div>
<!-- Blog Post (Right Sidebar) End -->
</div>
</div>
</div>
<!-- All Javascript Plugins -->
<script type="text/javascript" src="js/jquery.min.js"></script>
<script src="https://cdn.jsdelivr.net/npm/bootstrap@5.0.2/dist/js/bootstrap.bundle.min.js" integrity="sha384-MrcW6ZMFYlzcLA8Nl+NtUVF0sA7MsXsP1UyJoMp4YLEuNSfAP+JcXn/tWtIaxVXM" crossorigin="anonymous"></script>
<script type="text/javascript" src="js/prism4.js"></script>
<!-- Main Javascript File -->
<script type="text/javascript" src="js/scripts30.js"></script>
<!-- Google tag (gtag.js) -->
<script async src="https://www.googletagmanager.com/gtag/js?id=G-H8KZTWSQ1R"></script>
<script>
window.dataLayer = window.dataLayer || [];
function gtag(){dataLayer.push(arguments);}
gtag('js', new Date());
gtag('config', 'G-H8KZTWSQ1R');
</script>
</body>
</html>