(* Generated by coq-of-rust *)
Require Import CoqOfRust.CoqOfRust.

Module slice.
  Module sort.
    Module stable.
      Module drift.
        (*
        pub fn sort<T, F: FnMut(&T, &T) -> bool>(
            v: &mut [T],
            scratch: &mut [MaybeUninit<T>],
            eager_sort: bool,
            is_less: &mut F,
        ) {
            let len = v.len();
            if len < 2 {
                return; // Removing this length check *increases* code size.
            }
            let scale_factor = merge_tree_scale_factor(len);
        
            // It's important to have a relatively high entry barrier for pre-sorted
            // runs, as the presence of a single such run will force on average several
            // merge operations and shrink the maximum quicksort size a lot. For that
            // reason we use sqrt(len) as our pre-sorted run threshold.
            const MIN_SQRT_RUN_LEN: usize = 64;
            let min_good_run_len = if len <= (MIN_SQRT_RUN_LEN * MIN_SQRT_RUN_LEN) {
                // For small input length `MIN_SQRT_RUN_LEN` would break pattern
                // detection of full or nearly sorted inputs.
                cmp::min(len - len / 2, MIN_SQRT_RUN_LEN)
            } else {
                sqrt_approx(len)
            };
        
            // (stack_len, runs, desired_depths) together form a stack maintaining run
            // information for the powersort heuristic. desired_depths[i] is the desired
            // depth of the merge node that merges runs[i] with the run that comes after
            // it.
            let mut stack_len = 0;
            let mut run_storage = MaybeUninit::<[DriftsortRun; 66]>::uninit();
            let runs: *mut DriftsortRun = run_storage.as_mut_ptr().cast();
            let mut desired_depth_storage = MaybeUninit::<[u8; 66]>::uninit();
            let desired_depths: *mut u8 = desired_depth_storage.as_mut_ptr().cast();
        
            let mut scan_idx = 0;
            let mut prev_run = DriftsortRun::new_sorted(0); // Initial dummy run.
            loop {
                // Compute the next run and the desired depth of the merge node between
                // prev_run and next_run. On the last iteration we create a dummy run
                // with root-level desired depth to fully collapse the merge tree.
                let (next_run, desired_depth);
                if scan_idx < len {
                    next_run =
                        create_run(&mut v[scan_idx..], scratch, min_good_run_len, eager_sort, is_less);
                    desired_depth = merge_tree_depth(
                        scan_idx - prev_run.len(),
                        scan_idx,
                        scan_idx + next_run.len(),
                        scale_factor,
                    );
                } else {
                    next_run = DriftsortRun::new_sorted(0);
                    desired_depth = 0;
                };
        
                // Process the merge nodes between earlier runs[i] that have a desire to
                // be deeper in the merge tree than the merge node for the splitpoint
                // between prev_run and next_run.
                //
                // SAFETY: first note that this is the only place we modify stack_len,
                // runs or desired depths. We maintain the following invariants:
                //  1. The first stack_len elements of runs/desired_depths are initialized.
                //  2. For all valid i > 0, desired_depths[i] < desired_depths[i+1].
                //  3. The sum of all valid runs[i].len() plus prev_run.len() equals
                //     scan_idx.
                unsafe {
                    while stack_len > 1 && *desired_depths.add(stack_len - 1) >= desired_depth {
                        // Desired depth greater than the upcoming desired depth, pop
                        // left neighbor run from stack and merge into prev_run.
                        let left = *runs.add(stack_len - 1);
                        let merged_len = left.len() + prev_run.len();
                        let merge_start_idx = scan_idx - merged_len;
                        let merge_slice = v.get_unchecked_mut(merge_start_idx..scan_idx);
                        prev_run = logical_merge(merge_slice, scratch, left, prev_run, is_less);
                        stack_len -= 1;
                    }
        
                    // We now know that desired_depths[stack_len - 1] < desired_depth,
                    // maintaining our invariant. This also guarantees we don't overflow
                    // the stack as merge_tree_depth(..) <= 64 and thus we can only have
                    // 64 distinct values on the stack before pushing, plus our initial
                    // dummy run, while our capacity is 66.
                    *runs.add(stack_len) = prev_run;
                    *desired_depths.add(stack_len) = desired_depth;
                    stack_len += 1;
                }
        
                // Break before overriding the last run with our dummy run.
                if scan_idx >= len {
                    break;
                }
        
                scan_idx += next_run.len();
                prev_run = next_run;
            }
        
            if !prev_run.sorted() {
                stable_quicksort(v, scratch, is_less);
            }
        }
        *)
        Definition sort (ε : list Value.t) (τ : list Ty.t) (α : list Value.t) : M :=
          match ε, τ, α with
          | [], [ T; F ], [ v; scratch; eager_sort; is_less ] =>
            ltac:(M.monadic
              (let v := M.alloc (| v |) in
              let scratch := M.alloc (| scratch |) in
              let eager_sort := M.alloc (| eager_sort |) in
              let is_less := M.alloc (| is_less |) in
              M.catch_return (|
                ltac:(M.monadic
                  (M.read (|
                    let~ len :=
                      M.alloc (|
                        M.call_closure (|
                          M.get_associated_function (|
                            Ty.apply (Ty.path "slice") [] [ T ],
                            "len",
                            []
                          |),
                          [ M.read (| v |) ]
                        |)
                      |) in
                    let~ _ :=
                      M.match_operator (|
                        M.alloc (| Value.Tuple [] |),
                        [
                          fun γ =>
                            ltac:(M.monadic
                              (let γ :=
                                M.use
                                  (M.alloc (|
                                    BinOp.lt (|
                                      M.read (| len |),
                                      Value.Integer IntegerKind.Usize 2
                                    |)
                                  |)) in
                              let _ :=
                                M.is_constant_or_break_match (|
                                  M.read (| γ |),
                                  Value.Bool true
                                |) in
                              M.alloc (|
                                M.never_to_any (| M.read (| M.return_ (| Value.Tuple [] |) |) |)
                              |)));
                          fun γ => ltac:(M.monadic (M.alloc (| Value.Tuple [] |)))
                        ]
                      |) in
                    let~ scale_factor :=
                      M.alloc (|
                        M.call_closure (|
                          M.get_function (|
                            "core::slice::sort::stable::drift::merge_tree_scale_factor",
                            []
                          |),
                          [ M.read (| len |) ]
                        |)
                      |) in
                    let~ min_good_run_len :=
                      M.copy (|
                        M.match_operator (|
                          M.alloc (| Value.Tuple [] |),
                          [
                            fun γ =>
                              ltac:(M.monadic
                                (let γ :=
                                  M.use
                                    (M.alloc (|
                                      BinOp.le (|
                                        M.read (| len |),
                                        BinOp.Wrap.mul (|
                                          M.read (|
                                            M.get_constant (|
                                              "core::slice::sort::stable::drift::sort::MIN_SQRT_RUN_LEN"
                                            |)
                                          |),
                                          M.read (|
                                            M.get_constant (|
                                              "core::slice::sort::stable::drift::sort::MIN_SQRT_RUN_LEN"
                                            |)
                                          |)
                                        |)
                                      |)
                                    |)) in
                                let _ :=
                                  M.is_constant_or_break_match (|
                                    M.read (| γ |),
                                    Value.Bool true
                                  |) in
                                M.alloc (|
                                  M.call_closure (|
                                    M.get_function (| "core::cmp::min", [ Ty.path "usize" ] |),
                                    [
                                      BinOp.Wrap.sub (|
                                        M.read (| len |),
                                        BinOp.Wrap.div (|
                                          M.read (| len |),
                                          Value.Integer IntegerKind.Usize 2
                                        |)
                                      |);
                                      M.read (|
                                        M.get_constant (|
                                          "core::slice::sort::stable::drift::sort::MIN_SQRT_RUN_LEN"
                                        |)
                                      |)
                                    ]
                                  |)
                                |)));
                            fun γ =>
                              ltac:(M.monadic
                                (M.alloc (|
                                  M.call_closure (|
                                    M.get_function (|
                                      "core::slice::sort::stable::drift::sqrt_approx",
                                      []
                                    |),
                                    [ M.read (| len |) ]
                                  |)
                                |)))
                          ]
                        |)
                      |) in
                    let~ stack_len := M.alloc (| Value.Integer IntegerKind.Usize 0 |) in
                    let~ run_storage :=
                      M.alloc (|
                        M.call_closure (|
                          M.get_associated_function (|
                            Ty.apply
                              (Ty.path "core::mem::maybe_uninit::MaybeUninit")
                              []
                              [
                                Ty.apply
                                  (Ty.path "array")
                                  [ Value.Integer IntegerKind.Usize 66 ]
                                  [ Ty.path "core::slice::sort::stable::drift::DriftsortRun" ]
                              ],
                            "uninit",
                            []
                          |),
                          []
                        |)
                      |) in
                    let~ runs :=
                      M.alloc (|
                        M.call_closure (|
                          M.get_associated_function (|
                            Ty.apply
                              (Ty.path "*mut")
                              []
                              [
                                Ty.apply
                                  (Ty.path "array")
                                  [ Value.Integer IntegerKind.Usize 66 ]
                                  [ Ty.path "core::slice::sort::stable::drift::DriftsortRun" ]
                              ],
                            "cast",
                            [ Ty.path "core::slice::sort::stable::drift::DriftsortRun" ]
                          |),
                          [
                            M.call_closure (|
                              M.get_associated_function (|
                                Ty.apply
                                  (Ty.path "core::mem::maybe_uninit::MaybeUninit")
                                  []
                                  [
                                    Ty.apply
                                      (Ty.path "array")
                                      [ Value.Integer IntegerKind.Usize 66 ]
                                      [ Ty.path "core::slice::sort::stable::drift::DriftsortRun" ]
                                  ],
                                "as_mut_ptr",
                                []
                              |),
                              [ run_storage ]
                            |)
                          ]
                        |)
                      |) in
                    let~ desired_depth_storage :=
                      M.alloc (|
                        M.call_closure (|
                          M.get_associated_function (|
                            Ty.apply
                              (Ty.path "core::mem::maybe_uninit::MaybeUninit")
                              []
                              [
                                Ty.apply
                                  (Ty.path "array")
                                  [ Value.Integer IntegerKind.Usize 66 ]
                                  [ Ty.path "u8" ]
                              ],
                            "uninit",
                            []
                          |),
                          []
                        |)
                      |) in
                    let~ desired_depths :=
                      M.alloc (|
                        M.call_closure (|
                          M.get_associated_function (|
                            Ty.apply
                              (Ty.path "*mut")
                              []
                              [
                                Ty.apply
                                  (Ty.path "array")
                                  [ Value.Integer IntegerKind.Usize 66 ]
                                  [ Ty.path "u8" ]
                              ],
                            "cast",
                            [ Ty.path "u8" ]
                          |),
                          [
                            M.call_closure (|
                              M.get_associated_function (|
                                Ty.apply
                                  (Ty.path "core::mem::maybe_uninit::MaybeUninit")
                                  []
                                  [
                                    Ty.apply
                                      (Ty.path "array")
                                      [ Value.Integer IntegerKind.Usize 66 ]
                                      [ Ty.path "u8" ]
                                  ],
                                "as_mut_ptr",
                                []
                              |),
                              [ desired_depth_storage ]
                            |)
                          ]
                        |)
                      |) in
                    let~ scan_idx := M.alloc (| Value.Integer IntegerKind.Usize 0 |) in
                    let~ prev_run :=
                      M.alloc (|
                        M.call_closure (|
                          M.get_associated_function (|
                            Ty.path "core::slice::sort::stable::drift::DriftsortRun",
                            "new_sorted",
                            []
                          |),
                          [ Value.Integer IntegerKind.Usize 0 ]
                        |)
                      |) in
                    let~ _ :=
                      M.loop (|
                        ltac:(M.monadic
                          (M.match_operator (|
                            Value.DeclaredButUndefined,
                            [
                              fun γ =>
                                ltac:(M.monadic
                                  (let γ0_0 := M.SubPointer.get_tuple_field (| γ, 0 |) in
                                  let γ0_1 := M.SubPointer.get_tuple_field (| γ, 1 |) in
                                  let next_run := M.copy (| γ0_0 |) in
                                  let desired_depth := M.copy (| γ0_1 |) in
                                  let~ _ :=
                                    M.match_operator (|
                                      M.alloc (| Value.Tuple [] |),
                                      [
                                        fun γ =>
                                          ltac:(M.monadic
                                            (let γ :=
                                              M.use
                                                (M.alloc (|
                                                  BinOp.lt (|
                                                    M.read (| scan_idx |),
                                                    M.read (| len |)
                                                  |)
                                                |)) in
                                            let _ :=
                                              M.is_constant_or_break_match (|
                                                M.read (| γ |),
                                                Value.Bool true
                                              |) in
                                            let~ _ :=
                                              M.write (|
                                                next_run,
                                                M.call_closure (|
                                                  M.get_function (|
                                                    "core::slice::sort::stable::drift::create_run",
                                                    [ T; F ]
                                                  |),
                                                  [
                                                    M.call_closure (|
                                                      M.get_trait_method (|
                                                        "core::ops::index::IndexMut",
                                                        Ty.apply (Ty.path "slice") [] [ T ],
                                                        [
                                                          Ty.apply
                                                            (Ty.path "core::ops::range::RangeFrom")
                                                            []
                                                            [ Ty.path "usize" ]
                                                        ],
                                                        "index_mut",
                                                        []
                                                      |),
                                                      [
                                                        M.read (| v |);
                                                        Value.StructRecord
                                                          "core::ops::range::RangeFrom"
                                                          [ ("start", M.read (| scan_idx |)) ]
                                                      ]
                                                    |);
                                                    M.read (| scratch |);
                                                    M.read (| min_good_run_len |);
                                                    M.read (| eager_sort |);
                                                    M.read (| is_less |)
                                                  ]
                                                |)
                                              |) in
                                            let~ _ :=
                                              M.write (|
                                                desired_depth,
                                                M.call_closure (|
                                                  M.get_function (|
                                                    "core::slice::sort::stable::drift::merge_tree_depth",
                                                    []
                                                  |),
                                                  [
                                                    BinOp.Wrap.sub (|
                                                      M.read (| scan_idx |),
                                                      M.call_closure (|
                                                        M.get_associated_function (|
                                                          Ty.path
                                                            "core::slice::sort::stable::drift::DriftsortRun",
                                                          "len",
                                                          []
                                                        |),
                                                        [ M.read (| prev_run |) ]
                                                      |)
                                                    |);
                                                    M.read (| scan_idx |);
                                                    BinOp.Wrap.add (|
                                                      M.read (| scan_idx |),
                                                      M.call_closure (|
                                                        M.get_associated_function (|
                                                          Ty.path
                                                            "core::slice::sort::stable::drift::DriftsortRun",
                                                          "len",
                                                          []
                                                        |),
                                                        [ M.read (| next_run |) ]
                                                      |)
                                                    |);
                                                    M.read (| scale_factor |)
                                                  ]
                                                |)
                                              |) in
                                            M.alloc (| Value.Tuple [] |)));
                                        fun γ =>
                                          ltac:(M.monadic
                                            (let~ _ :=
                                              M.write (|
                                                next_run,
                                                M.call_closure (|
                                                  M.get_associated_function (|
                                                    Ty.path
                                                      "core::slice::sort::stable::drift::DriftsortRun",
                                                    "new_sorted",
                                                    []
                                                  |),
                                                  [ Value.Integer IntegerKind.Usize 0 ]
                                                |)
                                              |) in
                                            let~ _ :=
                                              M.write (|
                                                desired_depth,
                                                Value.Integer IntegerKind.U8 0
                                              |) in
                                            M.alloc (| Value.Tuple [] |)))
                                      ]
                                    |) in
                                  let~ _ :=
                                    let~ _ :=
                                      M.loop (|
                                        ltac:(M.monadic
                                          (M.match_operator (|
                                            M.alloc (| Value.Tuple [] |),
                                            [
                                              fun γ =>
                                                ltac:(M.monadic
                                                  (let γ :=
                                                    M.use
                                                      (M.alloc (|
                                                        LogicalOp.and (|
                                                          BinOp.gt (|
                                                            M.read (| stack_len |),
                                                            Value.Integer IntegerKind.Usize 1
                                                          |),
                                                          ltac:(M.monadic
                                                            (BinOp.ge (|
                                                              M.read (|
                                                                M.call_closure (|
                                                                  M.get_associated_function (|
                                                                    Ty.apply
                                                                      (Ty.path "*mut")
                                                                      []
                                                                      [ Ty.path "u8" ],
                                                                    "add",
                                                                    []
                                                                  |),
                                                                  [
                                                                    M.read (| desired_depths |);
                                                                    BinOp.Wrap.sub (|
                                                                      M.read (| stack_len |),
                                                                      Value.Integer
                                                                        IntegerKind.Usize
                                                                        1
                                                                    |)
                                                                  ]
                                                                |)
                                                              |),
                                                              M.read (| desired_depth |)
                                                            |)))
                                                        |)
                                                      |)) in
                                                  let _ :=
                                                    M.is_constant_or_break_match (|
                                                      M.read (| γ |),
                                                      Value.Bool true
                                                    |) in
                                                  let~ left :=
                                                    M.copy (|
                                                      M.call_closure (|
                                                        M.get_associated_function (|
                                                          Ty.apply
                                                            (Ty.path "*mut")
                                                            []
                                                            [
                                                              Ty.path
                                                                "core::slice::sort::stable::drift::DriftsortRun"
                                                            ],
                                                          "add",
                                                          []
                                                        |),
                                                        [
                                                          M.read (| runs |);
                                                          BinOp.Wrap.sub (|
                                                            M.read (| stack_len |),
                                                            Value.Integer IntegerKind.Usize 1
                                                          |)
                                                        ]
                                                      |)
                                                    |) in
                                                  let~ merged_len :=
                                                    M.alloc (|
                                                      BinOp.Wrap.add (|
                                                        M.call_closure (|
                                                          M.get_associated_function (|
                                                            Ty.path
                                                              "core::slice::sort::stable::drift::DriftsortRun",
                                                            "len",
                                                            []
                                                          |),
                                                          [ M.read (| left |) ]
                                                        |),
                                                        M.call_closure (|
                                                          M.get_associated_function (|
                                                            Ty.path
                                                              "core::slice::sort::stable::drift::DriftsortRun",
                                                            "len",
                                                            []
                                                          |),
                                                          [ M.read (| prev_run |) ]
                                                        |)
                                                      |)
                                                    |) in
                                                  let~ merge_start_idx :=
                                                    M.alloc (|
                                                      BinOp.Wrap.sub (|
                                                        M.read (| scan_idx |),
                                                        M.read (| merged_len |)
                                                      |)
                                                    |) in
                                                  let~ merge_slice :=
                                                    M.alloc (|
                                                      M.call_closure (|
                                                        M.get_associated_function (|
                                                          Ty.apply (Ty.path "slice") [] [ T ],
                                                          "get_unchecked_mut",
                                                          [
                                                            Ty.apply
                                                              (Ty.path "core::ops::range::Range")
                                                              []
                                                              [ Ty.path "usize" ]
                                                          ]
                                                        |),
                                                        [
                                                          M.read (| v |);
                                                          Value.StructRecord
                                                            "core::ops::range::Range"
                                                            [
                                                              ("start",
                                                                M.read (| merge_start_idx |));
                                                              ("end_", M.read (| scan_idx |))
                                                            ]
                                                        ]
                                                      |)
                                                    |) in
                                                  let~ _ :=
                                                    M.write (|
                                                      prev_run,
                                                      M.call_closure (|
                                                        M.get_function (|
                                                          "core::slice::sort::stable::drift::logical_merge",
                                                          [ T; F ]
                                                        |),
                                                        [
                                                          M.read (| merge_slice |);
                                                          M.read (| scratch |);
                                                          M.read (| left |);
                                                          M.read (| prev_run |);
                                                          M.read (| is_less |)
                                                        ]
                                                      |)
                                                    |) in
                                                  let~ _ :=
                                                    let β := stack_len in
                                                    M.write (|
                                                      β,
                                                      BinOp.Wrap.sub (|
                                                        M.read (| β |),
                                                        Value.Integer IntegerKind.Usize 1
                                                      |)
                                                    |) in
                                                  M.alloc (| Value.Tuple [] |)));
                                              fun γ =>
                                                ltac:(M.monadic
                                                  (M.alloc (|
                                                    M.never_to_any (|
                                                      M.read (|
                                                        let~ _ :=
                                                          M.alloc (|
                                                            M.never_to_any (|
                                                              M.read (| M.break (||) |)
                                                            |)
                                                          |) in
                                                        M.alloc (| Value.Tuple [] |)
                                                      |)
                                                    |)
                                                  |)))
                                            ]
                                          |)))
                                      |) in
                                    let~ _ :=
                                      M.write (|
                                        M.call_closure (|
                                          M.get_associated_function (|
                                            Ty.apply
                                              (Ty.path "*mut")
                                              []
                                              [
                                                Ty.path
                                                  "core::slice::sort::stable::drift::DriftsortRun"
                                              ],
                                            "add",
                                            []
                                          |),
                                          [ M.read (| runs |); M.read (| stack_len |) ]
                                        |),
                                        M.read (| prev_run |)
                                      |) in
                                    let~ _ :=
                                      M.write (|
                                        M.call_closure (|
                                          M.get_associated_function (|
                                            Ty.apply (Ty.path "*mut") [] [ Ty.path "u8" ],
                                            "add",
                                            []
                                          |),
                                          [ M.read (| desired_depths |); M.read (| stack_len |) ]
                                        |),
                                        M.read (| desired_depth |)
                                      |) in
                                    let~ _ :=
                                      let β := stack_len in
                                      M.write (|
                                        β,
                                        BinOp.Wrap.add (|
                                          M.read (| β |),
                                          Value.Integer IntegerKind.Usize 1
                                        |)
                                      |) in
                                    M.alloc (| Value.Tuple [] |) in
                                  let~ _ :=
                                    M.match_operator (|
                                      M.alloc (| Value.Tuple [] |),
                                      [
                                        fun γ =>
                                          ltac:(M.monadic
                                            (let γ :=
                                              M.use
                                                (M.alloc (|
                                                  BinOp.ge (|
                                                    M.read (| scan_idx |),
                                                    M.read (| len |)
                                                  |)
                                                |)) in
                                            let _ :=
                                              M.is_constant_or_break_match (|
                                                M.read (| γ |),
                                                Value.Bool true
                                              |) in
                                            M.alloc (|
                                              M.never_to_any (| M.read (| M.break (||) |) |)
                                            |)));
                                        fun γ => ltac:(M.monadic (M.alloc (| Value.Tuple [] |)))
                                      ]
                                    |) in
                                  let~ _ :=
                                    let β := scan_idx in
                                    M.write (|
                                      β,
                                      BinOp.Wrap.add (|
                                        M.read (| β |),
                                        M.call_closure (|
                                          M.get_associated_function (|
                                            Ty.path
                                              "core::slice::sort::stable::drift::DriftsortRun",
                                            "len",
                                            []
                                          |),
                                          [ M.read (| next_run |) ]
                                        |)
                                      |)
                                    |) in
                                  let~ _ := M.write (| prev_run, M.read (| next_run |) |) in
                                  M.alloc (| Value.Tuple [] |)))
                            ]
                          |)))
                      |) in
                    M.match_operator (|
                      M.alloc (| Value.Tuple [] |),
                      [
                        fun γ =>
                          ltac:(M.monadic
                            (let γ :=
                              M.use
                                (M.alloc (|
                                  UnOp.not (|
                                    M.call_closure (|
                                      M.get_associated_function (|
                                        Ty.path "core::slice::sort::stable::drift::DriftsortRun",
                                        "sorted",
                                        []
                                      |),
                                      [ M.read (| prev_run |) ]
                                    |)
                                  |)
                                |)) in
                            let _ :=
                              M.is_constant_or_break_match (| M.read (| γ |), Value.Bool true |) in
                            let~ _ :=
                              M.alloc (|
                                M.call_closure (|
                                  M.get_function (|
                                    "core::slice::sort::stable::drift::stable_quicksort",
                                    [ T; F ]
                                  |),
                                  [ M.read (| v |); M.read (| scratch |); M.read (| is_less |) ]
                                |)
                              |) in
                            M.alloc (| Value.Tuple [] |)));
                        fun γ => ltac:(M.monadic (M.alloc (| Value.Tuple [] |)))
                      ]
                    |)
                  |)))
              |)))
          | _, _, _ => M.impossible "wrong number of arguments"
          end.
        
        Axiom Function_sort : M.IsFunction "core::slice::sort::stable::drift::sort" sort.
        
        Module sort.
          Definition value_MIN_SQRT_RUN_LEN : Value.t :=
            M.run ltac:(M.monadic (M.alloc (| Value.Integer IntegerKind.Usize 64 |))).
        End sort.
        
        (*
        fn merge_tree_scale_factor(n: usize) -> u64 {
            if usize::BITS > u64::BITS {
                panic!("Platform not supported");
            }
        
            ((1 << 62) + n as u64 - 1) / n as u64
        }
        *)
        Definition merge_tree_scale_factor
            (ε : list Value.t)
            (τ : list Ty.t)
            (α : list Value.t)
            : M :=
          match ε, τ, α with
          | [], [], [ n ] =>
            ltac:(M.monadic
              (let n := M.alloc (| n |) in
              M.read (|
                let~ _ :=
                  M.match_operator (|
                    M.alloc (| Value.Tuple [] |),
                    [
                      fun γ =>
                        ltac:(M.monadic
                          (let γ :=
                            M.use
                              (M.alloc (|
                                BinOp.gt (|
                                  M.read (| M.get_constant (| "core::num::BITS" |) |),
                                  M.read (| M.get_constant (| "core::num::BITS" |) |)
                                |)
                              |)) in
                          let _ :=
                            M.is_constant_or_break_match (| M.read (| γ |), Value.Bool true |) in
                          M.alloc (|
                            M.never_to_any (|
                              M.call_closure (|
                                M.get_function (| "core::panicking::panic_fmt", [] |),
                                [
                                  M.call_closure (|
                                    M.get_associated_function (|
                                      Ty.path "core::fmt::Arguments",
                                      "new_const",
                                      []
                                    |),
                                    [
                                      M.alloc (|
                                        Value.Array
                                          [ M.read (| Value.String "Platform not supported" |) ]
                                      |)
                                    ]
                                  |)
                                ]
                              |)
                            |)
                          |)));
                      fun γ => ltac:(M.monadic (M.alloc (| Value.Tuple [] |)))
                    ]
                  |) in
                M.alloc (|
                  BinOp.Wrap.div (|
                    BinOp.Wrap.sub (|
                      BinOp.Wrap.add (|
                        BinOp.Wrap.shl (|
                          Value.Integer IntegerKind.U64 1,
                          Value.Integer IntegerKind.I32 62
                        |),
                        M.rust_cast (M.read (| n |))
                      |),
                      Value.Integer IntegerKind.U64 1
                    |),
                    M.rust_cast (M.read (| n |))
                  |)
                |)
              |)))
          | _, _, _ => M.impossible "wrong number of arguments"
          end.
        
        Axiom Function_merge_tree_scale_factor :
          M.IsFunction
            "core::slice::sort::stable::drift::merge_tree_scale_factor"
            merge_tree_scale_factor.
        
        (*
        fn merge_tree_depth(left: usize, mid: usize, right: usize, scale_factor: u64) -> u8 {
            let x = left as u64 + mid as u64;
            let y = mid as u64 + right as u64;
            ((scale_factor * x) ^ (scale_factor * y)).leading_zeros() as u8
        }
        *)
        Definition merge_tree_depth (ε : list Value.t) (τ : list Ty.t) (α : list Value.t) : M :=
          match ε, τ, α with
          | [], [], [ _ as left; mid; _ as right; scale_factor ] =>
            ltac:(M.monadic
              (let left := M.alloc (| left |) in
              let mid := M.alloc (| mid |) in
              let right := M.alloc (| right |) in
              let scale_factor := M.alloc (| scale_factor |) in
              M.read (|
                let~ x :=
                  M.alloc (|
                    BinOp.Wrap.add (|
                      M.rust_cast (M.read (| left |)),
                      M.rust_cast (M.read (| mid |))
                    |)
                  |) in
                let~ y :=
                  M.alloc (|
                    BinOp.Wrap.add (|
                      M.rust_cast (M.read (| mid |)),
                      M.rust_cast (M.read (| right |))
                    |)
                  |) in
                M.alloc (|
                  M.rust_cast
                    (M.call_closure (|
                      M.get_associated_function (| Ty.path "u64", "leading_zeros", [] |),
                      [
                        BinOp.bit_xor
                          (BinOp.Wrap.mul (| M.read (| scale_factor |), M.read (| x |) |))
                          (BinOp.Wrap.mul (| M.read (| scale_factor |), M.read (| y |) |))
                      ]
                    |))
                |)
              |)))
          | _, _, _ => M.impossible "wrong number of arguments"
          end.
        
        Axiom Function_merge_tree_depth :
          M.IsFunction "core::slice::sort::stable::drift::merge_tree_depth" merge_tree_depth.
        
        (*
        fn sqrt_approx(n: usize) -> usize {
            // Note that sqrt(n) = n^(1/2), and that 2^log2(n) = n. We combine these
            // two facts to approximate sqrt(n) as 2^(log2(n) / 2). Because our integer
            // log floors we want to add 0.5 to compensate for this on average, so our
            // initial approximation is 2^((1 + floor(log2(n))) / 2).
            //
            // We then apply an iteration of Newton's method to improve our
            // approximation, which for sqrt(n) is a1 = (a0 + n / a0) / 2.
            //
            // Finally we note that the exponentiation / division can be done directly
            // with shifts. We OR with 1 to avoid zero-checks in the integer log.
            let ilog = (n | 1).ilog2();
            let shift = (1 + ilog) / 2;
            ((1 << shift) + (n >> shift)) / 2
        }
        *)
        Definition sqrt_approx (ε : list Value.t) (τ : list Ty.t) (α : list Value.t) : M :=
          match ε, τ, α with
          | [], [], [ n ] =>
            ltac:(M.monadic
              (let n := M.alloc (| n |) in
              M.read (|
                let~ ilog :=
                  M.alloc (|
                    M.call_closure (|
                      M.get_associated_function (| Ty.path "usize", "ilog2", [] |),
                      [ BinOp.bit_or (M.read (| n |)) (Value.Integer IntegerKind.Usize 1) ]
                    |)
                  |) in
                let~ shift :=
                  M.alloc (|
                    BinOp.Wrap.div (|
                      BinOp.Wrap.add (| Value.Integer IntegerKind.U32 1, M.read (| ilog |) |),
                      Value.Integer IntegerKind.U32 2
                    |)
                  |) in
                M.alloc (|
                  BinOp.Wrap.div (|
                    BinOp.Wrap.add (|
                      BinOp.Wrap.shl (| Value.Integer IntegerKind.Usize 1, M.read (| shift |) |),
                      BinOp.Wrap.shr (| M.read (| n |), M.read (| shift |) |)
                    |),
                    Value.Integer IntegerKind.Usize 2
                  |)
                |)
              |)))
          | _, _, _ => M.impossible "wrong number of arguments"
          end.
        
        Axiom Function_sqrt_approx :
          M.IsFunction "core::slice::sort::stable::drift::sqrt_approx" sqrt_approx.
        
        (*
        fn logical_merge<T, F: FnMut(&T, &T) -> bool>(
            v: &mut [T],
            scratch: &mut [MaybeUninit<T>],
            left: DriftsortRun,
            right: DriftsortRun,
            is_less: &mut F,
        ) -> DriftsortRun {
            // If one or both of the runs are sorted do a physical merge, using
            // quicksort to sort the unsorted run if present. We also *need* to
            // physically merge if the combined runs would not fit in the scratch space
            // anymore (as this would mean we are no longer able to quicksort them).
            let len = v.len();
            let can_fit_in_scratch = len <= scratch.len();
            if !can_fit_in_scratch || left.sorted() || right.sorted() {
                if !left.sorted() {
                    stable_quicksort(&mut v[..left.len()], scratch, is_less);
                }
                if !right.sorted() {
                    stable_quicksort(&mut v[left.len()..], scratch, is_less);
                }
                merge(v, scratch, left.len(), is_less);
        
                DriftsortRun::new_sorted(len)
            } else {
                DriftsortRun::new_unsorted(len)
            }
        }
        *)
        Definition logical_merge (ε : list Value.t) (τ : list Ty.t) (α : list Value.t) : M :=
          match ε, τ, α with
          | [], [ T; F ], [ v; scratch; _ as left; _ as right; is_less ] =>
            ltac:(M.monadic
              (let v := M.alloc (| v |) in
              let scratch := M.alloc (| scratch |) in
              let left := M.alloc (| left |) in
              let right := M.alloc (| right |) in
              let is_less := M.alloc (| is_less |) in
              M.read (|
                let~ len :=
                  M.alloc (|
                    M.call_closure (|
                      M.get_associated_function (|
                        Ty.apply (Ty.path "slice") [] [ T ],
                        "len",
                        []
                      |),
                      [ M.read (| v |) ]
                    |)
                  |) in
                let~ can_fit_in_scratch :=
                  M.alloc (|
                    BinOp.le (|
                      M.read (| len |),
                      M.call_closure (|
                        M.get_associated_function (|
                          Ty.apply
                            (Ty.path "slice")
                            []
                            [ Ty.apply (Ty.path "core::mem::maybe_uninit::MaybeUninit") [] [ T ] ],
                          "len",
                          []
                        |),
                        [ M.read (| scratch |) ]
                      |)
                    |)
                  |) in
                M.match_operator (|
                  M.alloc (| Value.Tuple [] |),
                  [
                    fun γ =>
                      ltac:(M.monadic
                        (let γ :=
                          M.use
                            (M.alloc (|
                              LogicalOp.or (|
                                LogicalOp.or (|
                                  UnOp.not (| M.read (| can_fit_in_scratch |) |),
                                  ltac:(M.monadic
                                    (M.call_closure (|
                                      M.get_associated_function (|
                                        Ty.path "core::slice::sort::stable::drift::DriftsortRun",
                                        "sorted",
                                        []
                                      |),
                                      [ M.read (| left |) ]
                                    |)))
                                |),
                                ltac:(M.monadic
                                  (M.call_closure (|
                                    M.get_associated_function (|
                                      Ty.path "core::slice::sort::stable::drift::DriftsortRun",
                                      "sorted",
                                      []
                                    |),
                                    [ M.read (| right |) ]
                                  |)))
                              |)
                            |)) in
                        let _ :=
                          M.is_constant_or_break_match (| M.read (| γ |), Value.Bool true |) in
                        let~ _ :=
                          M.match_operator (|
                            M.alloc (| Value.Tuple [] |),
                            [
                              fun γ =>
                                ltac:(M.monadic
                                  (let γ :=
                                    M.use
                                      (M.alloc (|
                                        UnOp.not (|
                                          M.call_closure (|
                                            M.get_associated_function (|
                                              Ty.path
                                                "core::slice::sort::stable::drift::DriftsortRun",
                                              "sorted",
                                              []
                                            |),
                                            [ M.read (| left |) ]
                                          |)
                                        |)
                                      |)) in
                                  let _ :=
                                    M.is_constant_or_break_match (|
                                      M.read (| γ |),
                                      Value.Bool true
                                    |) in
                                  let~ _ :=
                                    M.alloc (|
                                      M.call_closure (|
                                        M.get_function (|
                                          "core::slice::sort::stable::drift::stable_quicksort",
                                          [ T; F ]
                                        |),
                                        [
                                          M.call_closure (|
                                            M.get_trait_method (|
                                              "core::ops::index::IndexMut",
                                              Ty.apply (Ty.path "slice") [] [ T ],
                                              [
                                                Ty.apply
                                                  (Ty.path "core::ops::range::RangeTo")
                                                  []
                                                  [ Ty.path "usize" ]
                                              ],
                                              "index_mut",
                                              []
                                            |),
                                            [
                                              M.read (| v |);
                                              Value.StructRecord
                                                "core::ops::range::RangeTo"
                                                [
                                                  ("end_",
                                                    M.call_closure (|
                                                      M.get_associated_function (|
                                                        Ty.path
                                                          "core::slice::sort::stable::drift::DriftsortRun",
                                                        "len",
                                                        []
                                                      |),
                                                      [ M.read (| left |) ]
                                                    |))
                                                ]
                                            ]
                                          |);
                                          M.read (| scratch |);
                                          M.read (| is_less |)
                                        ]
                                      |)
                                    |) in
                                  M.alloc (| Value.Tuple [] |)));
                              fun γ => ltac:(M.monadic (M.alloc (| Value.Tuple [] |)))
                            ]
                          |) in
                        let~ _ :=
                          M.match_operator (|
                            M.alloc (| Value.Tuple [] |),
                            [
                              fun γ =>
                                ltac:(M.monadic
                                  (let γ :=
                                    M.use
                                      (M.alloc (|
                                        UnOp.not (|
                                          M.call_closure (|
                                            M.get_associated_function (|
                                              Ty.path
                                                "core::slice::sort::stable::drift::DriftsortRun",
                                              "sorted",
                                              []
                                            |),
                                            [ M.read (| right |) ]
                                          |)
                                        |)
                                      |)) in
                                  let _ :=
                                    M.is_constant_or_break_match (|
                                      M.read (| γ |),
                                      Value.Bool true
                                    |) in
                                  let~ _ :=
                                    M.alloc (|
                                      M.call_closure (|
                                        M.get_function (|
                                          "core::slice::sort::stable::drift::stable_quicksort",
                                          [ T; F ]
                                        |),
                                        [
                                          M.call_closure (|
                                            M.get_trait_method (|
                                              "core::ops::index::IndexMut",
                                              Ty.apply (Ty.path "slice") [] [ T ],
                                              [
                                                Ty.apply
                                                  (Ty.path "core::ops::range::RangeFrom")
                                                  []
                                                  [ Ty.path "usize" ]
                                              ],
                                              "index_mut",
                                              []
                                            |),
                                            [
                                              M.read (| v |);
                                              Value.StructRecord
                                                "core::ops::range::RangeFrom"
                                                [
                                                  ("start",
                                                    M.call_closure (|
                                                      M.get_associated_function (|
                                                        Ty.path
                                                          "core::slice::sort::stable::drift::DriftsortRun",
                                                        "len",
                                                        []
                                                      |),
                                                      [ M.read (| left |) ]
                                                    |))
                                                ]
                                            ]
                                          |);
                                          M.read (| scratch |);
                                          M.read (| is_less |)
                                        ]
                                      |)
                                    |) in
                                  M.alloc (| Value.Tuple [] |)));
                              fun γ => ltac:(M.monadic (M.alloc (| Value.Tuple [] |)))
                            ]
                          |) in
                        let~ _ :=
                          M.alloc (|
                            M.call_closure (|
                              M.get_function (|
                                "core::slice::sort::stable::merge::merge",
                                [ T; F ]
                              |),
                              [
                                M.read (| v |);
                                M.read (| scratch |);
                                M.call_closure (|
                                  M.get_associated_function (|
                                    Ty.path "core::slice::sort::stable::drift::DriftsortRun",
                                    "len",
                                    []
                                  |),
                                  [ M.read (| left |) ]
                                |);
                                M.read (| is_less |)
                              ]
                            |)
                          |) in
                        M.alloc (|
                          M.call_closure (|
                            M.get_associated_function (|
                              Ty.path "core::slice::sort::stable::drift::DriftsortRun",
                              "new_sorted",
                              []
                            |),
                            [ M.read (| len |) ]
                          |)
                        |)));
                    fun γ =>
                      ltac:(M.monadic
                        (M.alloc (|
                          M.call_closure (|
                            M.get_associated_function (|
                              Ty.path "core::slice::sort::stable::drift::DriftsortRun",
                              "new_unsorted",
                              []
                            |),
                            [ M.read (| len |) ]
                          |)
                        |)))
                  ]
                |)
              |)))
          | _, _, _ => M.impossible "wrong number of arguments"
          end.
        
        Axiom Function_logical_merge :
          M.IsFunction "core::slice::sort::stable::drift::logical_merge" logical_merge.
        
        (*
        fn create_run<T, F: FnMut(&T, &T) -> bool>(
            v: &mut [T],
            scratch: &mut [MaybeUninit<T>],
            min_good_run_len: usize,
            eager_sort: bool,
            is_less: &mut F,
        ) -> DriftsortRun {
            let len = v.len();
            if len >= min_good_run_len {
                let (run_len, was_reversed) = find_existing_run(v, is_less);
        
                // SAFETY: find_existing_run promises to return a valid run_len.
                unsafe { intrinsics::assume(run_len <= len) };
        
                if run_len >= min_good_run_len {
                    if was_reversed {
                        v[..run_len].reverse();
                    }
        
                    return DriftsortRun::new_sorted(run_len);
                }
            }
        
            if eager_sort {
                // We call quicksort with a len that will immediately call small-sort.
                // By not calling the small-sort directly here it can always be inlined into
                // the quicksort itself, making the recursive base case faster and is generally
                // more binary-size efficient.
                let eager_run_len = cmp::min(T::small_sort_threshold(), len);
                quicksort(&mut v[..eager_run_len], scratch, 0, None, is_less);
                DriftsortRun::new_sorted(eager_run_len)
            } else {
                DriftsortRun::new_unsorted(cmp::min(min_good_run_len, len))
            }
        }
        *)
        Definition create_run (ε : list Value.t) (τ : list Ty.t) (α : list Value.t) : M :=
          match ε, τ, α with
          | [], [ T; F ], [ v; scratch; min_good_run_len; eager_sort; is_less ] =>
            ltac:(M.monadic
              (let v := M.alloc (| v |) in
              let scratch := M.alloc (| scratch |) in
              let min_good_run_len := M.alloc (| min_good_run_len |) in
              let eager_sort := M.alloc (| eager_sort |) in
              let is_less := M.alloc (| is_less |) in
              M.catch_return (|
                ltac:(M.monadic
                  (M.read (|
                    let~ len :=
                      M.alloc (|
                        M.call_closure (|
                          M.get_associated_function (|
                            Ty.apply (Ty.path "slice") [] [ T ],
                            "len",
                            []
                          |),
                          [ M.read (| v |) ]
                        |)
                      |) in
                    let~ _ :=
                      M.match_operator (|
                        M.alloc (| Value.Tuple [] |),
                        [
                          fun γ =>
                            ltac:(M.monadic
                              (let γ :=
                                M.use
                                  (M.alloc (|
                                    BinOp.ge (| M.read (| len |), M.read (| min_good_run_len |) |)
                                  |)) in
                              let _ :=
                                M.is_constant_or_break_match (|
                                  M.read (| γ |),
                                  Value.Bool true
                                |) in
                              M.match_operator (|
                                M.alloc (|
                                  M.call_closure (|
                                    M.get_function (|
                                      "core::slice::sort::shared::find_existing_run",
                                      [ T; F ]
                                    |),
                                    [ M.read (| v |); M.read (| is_less |) ]
                                  |)
                                |),
                                [
                                  fun γ =>
                                    ltac:(M.monadic
                                      (let γ0_0 := M.SubPointer.get_tuple_field (| γ, 0 |) in
                                      let γ0_1 := M.SubPointer.get_tuple_field (| γ, 1 |) in
                                      let run_len := M.copy (| γ0_0 |) in
                                      let was_reversed := M.copy (| γ0_1 |) in
                                      let~ _ :=
                                        M.alloc (|
                                          M.call_closure (|
                                            M.get_function (| "core::intrinsics::assume", [] |),
                                            [ BinOp.le (| M.read (| run_len |), M.read (| len |) |)
                                            ]
                                          |)
                                        |) in
                                      M.match_operator (|
                                        M.alloc (| Value.Tuple [] |),
                                        [
                                          fun γ =>
                                            ltac:(M.monadic
                                              (let γ :=
                                                M.use
                                                  (M.alloc (|
                                                    BinOp.ge (|
                                                      M.read (| run_len |),
                                                      M.read (| min_good_run_len |)
                                                    |)
                                                  |)) in
                                              let _ :=
                                                M.is_constant_or_break_match (|
                                                  M.read (| γ |),
                                                  Value.Bool true
                                                |) in
                                              M.alloc (|
                                                M.never_to_any (|
                                                  M.read (|
                                                    let~ _ :=
                                                      M.match_operator (|
                                                        M.alloc (| Value.Tuple [] |),
                                                        [
                                                          fun γ =>
                                                            ltac:(M.monadic
                                                              (let γ := M.use was_reversed in
                                                              let _ :=
                                                                M.is_constant_or_break_match (|
                                                                  M.read (| γ |),
                                                                  Value.Bool true
                                                                |) in
                                                              let~ _ :=
                                                                M.alloc (|
                                                                  M.call_closure (|
                                                                    M.get_associated_function (|
                                                                      Ty.apply
                                                                        (Ty.path "slice")
                                                                        []
                                                                        [ T ],
                                                                      "reverse",
                                                                      []
                                                                    |),
                                                                    [
                                                                      M.call_closure (|
                                                                        M.get_trait_method (|
                                                                          "core::ops::index::IndexMut",
                                                                          Ty.apply
                                                                            (Ty.path "slice")
                                                                            []
                                                                            [ T ],
                                                                          [
                                                                            Ty.apply
                                                                              (Ty.path
                                                                                "core::ops::range::RangeTo")
                                                                              []
                                                                              [ Ty.path "usize" ]
                                                                          ],
                                                                          "index_mut",
                                                                          []
                                                                        |),
                                                                        [
                                                                          M.read (| v |);
                                                                          Value.StructRecord
                                                                            "core::ops::range::RangeTo"
                                                                            [
                                                                              ("end_",
                                                                                M.read (|
                                                                                  run_len
                                                                                |))
                                                                            ]
                                                                        ]
                                                                      |)
                                                                    ]
                                                                  |)
                                                                |) in
                                                              M.alloc (| Value.Tuple [] |)));
                                                          fun γ =>
                                                            ltac:(M.monadic
                                                              (M.alloc (| Value.Tuple [] |)))
                                                        ]
                                                      |) in
                                                    M.return_ (|
                                                      M.call_closure (|
                                                        M.get_associated_function (|
                                                          Ty.path
                                                            "core::slice::sort::stable::drift::DriftsortRun",
                                                          "new_sorted",
                                                          []
                                                        |),
                                                        [ M.read (| run_len |) ]
                                                      |)
                                                    |)
                                                  |)
                                                |)
                                              |)));
                                          fun γ => ltac:(M.monadic (M.alloc (| Value.Tuple [] |)))
                                        ]
                                      |)))
                                ]
                              |)));
                          fun γ => ltac:(M.monadic (M.alloc (| Value.Tuple [] |)))
                        ]
                      |) in
                    M.match_operator (|
                      M.alloc (| Value.Tuple [] |),
                      [
                        fun γ =>
                          ltac:(M.monadic
                            (let γ := M.use eager_sort in
                            let _ :=
                              M.is_constant_or_break_match (| M.read (| γ |), Value.Bool true |) in
                            let~ eager_run_len :=
                              M.alloc (|
                                M.call_closure (|
                                  M.get_function (| "core::cmp::min", [ Ty.path "usize" ] |),
                                  [
                                    M.call_closure (|
                                      M.get_trait_method (|
                                        "core::slice::sort::shared::smallsort::StableSmallSortTypeImpl",
                                        T,
                                        [],
                                        "small_sort_threshold",
                                        []
                                      |),
                                      []
                                    |);
                                    M.read (| len |)
                                  ]
                                |)
                              |) in
                            let~ _ :=
                              M.alloc (|
                                M.call_closure (|
                                  M.get_function (|
                                    "core::slice::sort::stable::quicksort::quicksort",
                                    [ T; F ]
                                  |),
                                  [
                                    M.call_closure (|
                                      M.get_trait_method (|
                                        "core::ops::index::IndexMut",
                                        Ty.apply (Ty.path "slice") [] [ T ],
                                        [
                                          Ty.apply
                                            (Ty.path "core::ops::range::RangeTo")
                                            []
                                            [ Ty.path "usize" ]
                                        ],
                                        "index_mut",
                                        []
                                      |),
                                      [
                                        M.read (| v |);
                                        Value.StructRecord
                                          "core::ops::range::RangeTo"
                                          [ ("end_", M.read (| eager_run_len |)) ]
                                      ]
                                    |);
                                    M.read (| scratch |);
                                    Value.Integer IntegerKind.U32 0;
                                    Value.StructTuple "core::option::Option::None" [];
                                    M.read (| is_less |)
                                  ]
                                |)
                              |) in
                            M.alloc (|
                              M.call_closure (|
                                M.get_associated_function (|
                                  Ty.path "core::slice::sort::stable::drift::DriftsortRun",
                                  "new_sorted",
                                  []
                                |),
                                [ M.read (| eager_run_len |) ]
                              |)
                            |)));
                        fun γ =>
                          ltac:(M.monadic
                            (M.alloc (|
                              M.call_closure (|
                                M.get_associated_function (|
                                  Ty.path "core::slice::sort::stable::drift::DriftsortRun",
                                  "new_unsorted",
                                  []
                                |),
                                [
                                  M.call_closure (|
                                    M.get_function (| "core::cmp::min", [ Ty.path "usize" ] |),
                                    [ M.read (| min_good_run_len |); M.read (| len |) ]
                                  |)
                                ]
                              |)
                            |)))
                      ]
                    |)
                  |)))
              |)))
          | _, _, _ => M.impossible "wrong number of arguments"
          end.
        
        Axiom Function_create_run :
          M.IsFunction "core::slice::sort::stable::drift::create_run" create_run.
        
        (*
        fn stable_quicksort<T, F: FnMut(&T, &T) -> bool>(
            v: &mut [T],
            scratch: &mut [MaybeUninit<T>],
            is_less: &mut F,
        ) {
            // Limit the number of imbalanced partitions to `2 * floor(log2(len))`.
            // The binary OR by one is used to eliminate the zero-check in the logarithm.
            let limit = 2 * (v.len() | 1).ilog2();
            quicksort(v, scratch, limit, None, is_less);
        }
        *)
        Definition stable_quicksort (ε : list Value.t) (τ : list Ty.t) (α : list Value.t) : M :=
          match ε, τ, α with
          | [], [ T; F ], [ v; scratch; is_less ] =>
            ltac:(M.monadic
              (let v := M.alloc (| v |) in
              let scratch := M.alloc (| scratch |) in
              let is_less := M.alloc (| is_less |) in
              M.read (|
                let~ limit :=
                  M.alloc (|
                    BinOp.Wrap.mul (|
                      Value.Integer IntegerKind.U32 2,
                      M.call_closure (|
                        M.get_associated_function (| Ty.path "usize", "ilog2", [] |),
                        [
                          BinOp.bit_or
                            (M.call_closure (|
                              M.get_associated_function (|
                                Ty.apply (Ty.path "slice") [] [ T ],
                                "len",
                                []
                              |),
                              [ M.read (| v |) ]
                            |))
                            (Value.Integer IntegerKind.Usize 1)
                        ]
                      |)
                    |)
                  |) in
                let~ _ :=
                  M.alloc (|
                    M.call_closure (|
                      M.get_function (|
                        "core::slice::sort::stable::quicksort::quicksort",
                        [ T; F ]
                      |),
                      [
                        M.read (| v |);
                        M.read (| scratch |);
                        M.read (| limit |);
                        Value.StructTuple "core::option::Option::None" [];
                        M.read (| is_less |)
                      ]
                    |)
                  |) in
                M.alloc (| Value.Tuple [] |)
              |)))
          | _, _, _ => M.impossible "wrong number of arguments"
          end.
        
        Axiom Function_stable_quicksort :
          M.IsFunction "core::slice::sort::stable::drift::stable_quicksort" stable_quicksort.
        
        (* StructTuple
          {
            name := "DriftsortRun";
            const_params := [];
            ty_params := [];
            fields := [ Ty.path "usize" ];
          } *)
        
        Module Impl_core_marker_Copy_for_core_slice_sort_stable_drift_DriftsortRun.
          Definition Self : Ty.t := Ty.path "core::slice::sort::stable::drift::DriftsortRun".
          
          Axiom Implements :
            M.IsTraitInstance
              "core::marker::Copy"
              Self
              (* Trait polymorphic types *) []
              (* Instance *) [].
        End Impl_core_marker_Copy_for_core_slice_sort_stable_drift_DriftsortRun.
        
        Module Impl_core_clone_Clone_for_core_slice_sort_stable_drift_DriftsortRun.
          Definition Self : Ty.t := Ty.path "core::slice::sort::stable::drift::DriftsortRun".
          
          (* Clone *)
          Definition clone (ε : list Value.t) (τ : list Ty.t) (α : list Value.t) : M :=
            match ε, τ, α with
            | [], [], [ self ] =>
              ltac:(M.monadic
                (let self := M.alloc (| self |) in
                M.read (|
                  M.match_operator (|
                    Value.DeclaredButUndefined,
                    [ fun γ => ltac:(M.monadic (M.read (| self |))) ]
                  |)
                |)))
            | _, _, _ => M.impossible "wrong number of arguments"
            end.
          
          Axiom Implements :
            M.IsTraitInstance
              "core::clone::Clone"
              Self
              (* Trait polymorphic types *) []
              (* Instance *) [ ("clone", InstanceField.Method clone) ].
        End Impl_core_clone_Clone_for_core_slice_sort_stable_drift_DriftsortRun.
        
        Module Impl_core_slice_sort_stable_drift_DriftsortRun.
          Definition Self : Ty.t := Ty.path "core::slice::sort::stable::drift::DriftsortRun".
          
          (*
              fn new_sorted(length: usize) -> Self {
                  Self((length << 1) | 1)
              }
          *)
          Definition new_sorted (ε : list Value.t) (τ : list Ty.t) (α : list Value.t) : M :=
            match ε, τ, α with
            | [], [], [ length ] =>
              ltac:(M.monadic
                (let length := M.alloc (| length |) in
                Value.StructTuple
                  "core::slice::sort::stable::drift::DriftsortRun"
                  [
                    BinOp.bit_or
                      (BinOp.Wrap.shl (| M.read (| length |), Value.Integer IntegerKind.I32 1 |))
                      (Value.Integer IntegerKind.Usize 1)
                  ]))
            | _, _, _ => M.impossible "wrong number of arguments"
            end.
          
          Axiom AssociatedFunction_new_sorted : M.IsAssociatedFunction Self "new_sorted" new_sorted.
          
          (*
              fn new_unsorted(length: usize) -> Self {
                  Self(length << 1)
              }
          *)
          Definition new_unsorted (ε : list Value.t) (τ : list Ty.t) (α : list Value.t) : M :=
            match ε, τ, α with
            | [], [], [ length ] =>
              ltac:(M.monadic
                (let length := M.alloc (| length |) in
                Value.StructTuple
                  "core::slice::sort::stable::drift::DriftsortRun"
                  [ BinOp.Wrap.shl (| M.read (| length |), Value.Integer IntegerKind.I32 1 |) ]))
            | _, _, _ => M.impossible "wrong number of arguments"
            end.
          
          Axiom AssociatedFunction_new_unsorted :
            M.IsAssociatedFunction Self "new_unsorted" new_unsorted.
          
          (*
              fn sorted(self) -> bool {
                  self.0 & 1 == 1
              }
          *)
          Definition sorted (ε : list Value.t) (τ : list Ty.t) (α : list Value.t) : M :=
            match ε, τ, α with
            | [], [], [ self ] =>
              ltac:(M.monadic
                (let self := M.alloc (| self |) in
                BinOp.eq (|
                  BinOp.bit_and
                    (M.read (|
                      M.SubPointer.get_struct_tuple_field (|
                        self,
                        "core::slice::sort::stable::drift::DriftsortRun",
                        0
                      |)
                    |))
                    (Value.Integer IntegerKind.Usize 1),
                  Value.Integer IntegerKind.Usize 1
                |)))
            | _, _, _ => M.impossible "wrong number of arguments"
            end.
          
          Axiom AssociatedFunction_sorted : M.IsAssociatedFunction Self "sorted" sorted.
          
          (*
              fn len(self) -> usize {
                  self.0 >> 1
              }
          *)
          Definition len (ε : list Value.t) (τ : list Ty.t) (α : list Value.t) : M :=
            match ε, τ, α with
            | [], [], [ self ] =>
              ltac:(M.monadic
                (let self := M.alloc (| self |) in
                BinOp.Wrap.shr (|
                  M.read (|
                    M.SubPointer.get_struct_tuple_field (|
                      self,
                      "core::slice::sort::stable::drift::DriftsortRun",
                      0
                    |)
                  |),
                  Value.Integer IntegerKind.I32 1
                |)))
            | _, _, _ => M.impossible "wrong number of arguments"
            end.
          
          Axiom AssociatedFunction_len : M.IsAssociatedFunction Self "len" len.
        End Impl_core_slice_sort_stable_drift_DriftsortRun.
      End drift.
    End stable.
  End sort.
End slice.
