952 /// Merges non-decreasing runs `v[..mid]` and `v[mid..]` using `buf` as temporary storage, and
1072 /// natural runs. There is a stack of pending runs yet to be merged. Each newly found run is pushed
1073 /// onto the stack, and then some pairs of adjacent runs are merged until these two invariants are
1076 /// 1. for every `i` in `1..runs.len()`: `runs[i - 1].len > runs[i].len`
1077 /// 2. for every `i` in `2..runs.len()`: `runs[i - 2].len > runs[i - 1].len + runs[i].len`
1087     // Very short runs are extended using insertion sort to span at least this many elements.  in merge_sort()
1109     // `is_less` panics. When merging two sorted runs, this buffer holds a copy of the shorter run,  in merge_sort()
1113     // In order to identify natural runs in `v`, we traverse it backwards. That might seem like a  in merge_sort()
1116     // backwards. To conclude, identifying runs by traversing backwards improves performance.  in merge_sort()
1117     let mut runs = vec![];  in merge_sort()  localVariable
1147         runs.push(Run { start, len: end - start });  in merge_sort()
1150         // Merge some pairs of adjacent runs to satisfy the invariants.  in merge_sort()
1151         while let Some(r) = collapse(&runs) {  in merge_sort()
1152             let left = runs[r + 1];  in merge_sort()
1153             let right = runs[r];  in merge_sort()
1162             runs[r] = Run { start: left.start, len: left.len + right.len };  in merge_sort()
1163             runs.remove(r + 1);  in merge_sort()
1168     debug_assert!(runs.len() == 1 && runs[0].start == 0 && runs[0].len == len);  in merge_sort()
1170     // Examines the stack of runs and identifies the next pair of runs to merge. More specifically,  in merge_sort()
1171     // if `Some(r)` is returned, that means `runs[r]` and `runs[r + 1]` must be merged next. If the  in merge_sort()
1177     // The gist of the story is: we must enforce the invariants on the top four runs on the stack.  in merge_sort()
1179     // hold for *all* runs in the stack.  in merge_sort()
1181     // This function correctly checks invariants for the top four runs. Additionally, if the top  in merge_sort()
1185     fn collapse(runs: &[Run]) -> Option<usize> {  in merge_sort()
1186         let n = runs.len();  in merge_sort()
1188             && (runs[n - 1].start == 0  in merge_sort()
1189                 || runs[n - 2].len <= runs[n - 1].len  in merge_sort()
1190                 || (n >= 3 && runs[n - 3].len <= runs[n - 2].len + runs[n - 1].len)  in merge_sort()
1191                 || (n >= 4 && runs[n - 4].len <= runs[n - 3].len + runs[n - 2].len))  in merge_sort()
1193             if n >= 3 && runs[n - 3].len < runs[n - 1].len { Some(n - 3) } else { Some(n - 2) }  in merge_sort()