Decoded: OpenTTD (2003) v1.8 (2018)
Source file: sort_func.hpp
Line-by-line code walkthrough by MaiZure

sort_func.hpp defines quicksort and gnome sort functions

Original code:
https://github.com/MaiZure/OpenTTD-1.8/blob/master/src/core/sort_func.hpp





1     COMMENT (*)
2     BLANK (-)
3     *
4     *
5     *
6     *
7     *
8     *
9     -
10    *
11    -
12    Header guard
13    Header guard
14    -
15    Includes the OpenTTD memory function header
16    -
17    *
18    *
19    *
20    *
21    *
22    *
23    *
24    *
25    *
26    *
27    Sets up a class template with a single type parameter
28    Defines QSortT with  4 arguments: a base object pointer, a count, a comparator
      function, and an order flag
29    BLOCK START - QSortT, type-safe qsort using the built-in qsort
30    If there are less than 2 items, there's nothing to sort
31    -
32    Pass arguments to qsort after converting type count to size
33    -
34    If we're ordering by descending, reverse the memory order of items
35    BLOCK END - QSortT
36    -
37    *
38    *
39    *
40    *
41    *
42    *
43    *
44    *
45    *
46    *
47    *
48    *
49    *
50    *
51    Sets up a class template with a type parameter
52    Defines GSort with 4 arguments: a base object pointer, a count, a comparator
      function, and an order flag
53    BLOCK START - GSortT
54    If there are less than 2 objects, there's nothing to sort
55    -
56    Verify that the base object exists
57    Verify that the comparator exists
58    -
59    Get a pointer to the base object
60    Get a pointer to the subsequent object
61    Initalize an offset (From base) to 0
62    -
63    Loop while there are objects remaining to sort
64    Store the difference between the items
65    If no move needs to happen based on the desired order...
66    But we've recently performed a swap...
67    *
68    Advance the first object by the last used offset
69    Advance the second object by the last used offset
70    Reset the offset
71    Move to next item
72    End check for recent large offset
73    -
74    Advance first object pointer by 1
75    Advance second object pointer by 1
76    One less set to check
77    Otherwise, the items are not properly ordered...
78    Swap the items
79    -
80    If we're already at the start, just skip to the next check
81    -
82    Need to recheck last after the swap, decrement first object
83    Decrement the second object
84    Advance the offset to scan
85    End swap case
86    Repeat loop while unsorted objects remain
87    BLOCK END - GSortT
88    -
89    Header guard end