<s> """<STR_LIT>""" <EOL> from __future__ import print_function , absolute_import , division <EOL> import collections <EOL> from numba import types <EOL> TimsortImplementation = collections . namedtuple ( <EOL> '<STR_LIT>' , <EOL> ( <EOL> '<STR_LIT>' , <EOL> '<STR_LIT>' , '<STR_LIT>' , '<STR_LIT>' , '<STR_LIT>' , <EOL> '<STR_LIT>' , '<STR_LIT>' , '<STR_LIT>' , <EOL> '<STR_LIT>' , '<STR_LIT>' , '<STR_LIT>' , '<STR_LIT>' , <EOL> '<STR_LIT>' , '<STR_LIT>' , <EOL> '<STR_LIT>' , '<STR_LIT>' <EOL> ) ) <EOL> MAX_MERGE_PENDING = <NUM_LIT> <EOL> MIN_GALLOP = <NUM_LIT:7> <EOL> MERGESTATE_TEMP_SIZE = <NUM_LIT> <EOL> MergeState = collections . namedtuple ( <EOL> '<STR_LIT>' , ( '<STR_LIT>' , '<STR_LIT>' , '<STR_LIT>' , '<STR_LIT>' , '<STR_LIT:n>' ) ) <EOL> MergeRun = collections . namedtuple ( '<STR_LIT>' , ( '<STR_LIT:start>' , '<STR_LIT:size>' ) ) <EOL> def make_timsort_impl ( wrap , make_temp_area ) : <EOL> make_temp_area = wrap ( make_temp_area ) <EOL> intp = types . intp <EOL> zero = intp ( <NUM_LIT:0> ) <EOL> @ wrap <EOL> def has_values ( keys , values ) : <EOL> return values is not keys <EOL> @ wrap <EOL> def merge_init ( keys ) : <EOL> """<STR_LIT>""" <EOL> temp_size = min ( len ( keys ) // <NUM_LIT:2> + <NUM_LIT:1> , MERGESTATE_TEMP_SIZE ) <EOL> temp_keys = make_temp_area ( keys , temp_size ) <EOL> temp_values = temp_keys <EOL> pending = [ MergeRun ( zero , zero ) ] * MAX_MERGE_PENDING <EOL> return MergeState ( intp ( MIN_GALLOP ) , temp_keys , temp_values , pending , zero ) <EOL> @ wrap <EOL> def merge_init_with_values ( keys , values ) : <EOL> """<STR_LIT>""" <EOL> temp_size = min ( len ( keys ) // <NUM_LIT:2> + <NUM_LIT:1> , MERGESTATE_TEMP_SIZE ) <EOL> temp_keys = make_temp_area ( keys , temp_size ) <EOL> temp_values = make_temp_area ( values , temp_size ) <EOL> pending = [ MergeRun ( zero , zero ) ] * MAX_MERGE_PENDING <EOL> return MergeState ( intp ( MIN_GALLOP ) , temp_keys , temp_values , pending , zero ) <EOL> @ wrap <EOL> def merge_append ( ms , run ) : <EOL> """<STR_LIT>""" <EOL> n = ms . n <EOL> assert n < MAX_MERGE_PENDING <EOL> ms . pending [ n ] = run <EOL> return MergeState ( ms . min_gallop , ms . keys , ms . values , ms . pending , n + <NUM_LIT:1> ) <EOL> @ wrap <EOL> def merge_pop ( ms ) : <EOL> """<STR_LIT>""" <EOL> return MergeState ( ms . min_gallop , ms . keys , ms . values , ms . pending , ms . n - <NUM_LIT:1> ) <EOL> @ wrap <EOL> def merge_getmem ( ms , need ) : <EOL> """<STR_LIT>""" <EOL> alloced = len ( ms . keys ) <EOL> if need <= alloced : <EOL> return ms <EOL> while alloced < need : <EOL> alloced = alloced << <NUM_LIT:1> <EOL> temp_keys = make_temp_area ( ms . keys , alloced ) <EOL> if has_values ( ms . keys , ms . values ) : <EOL> temp_values = make_temp_area ( ms . values , alloced ) <EOL> else : <EOL> temp_values = temp_keys <EOL> return MergeState ( ms . min_gallop , temp_keys , temp_values , ms . pending , ms . n ) <EOL> @ wrap <EOL> def merge_adjust_gallop ( ms , new_gallop ) : <EOL> """<STR_LIT>""" <EOL> return MergeState ( intp ( new_gallop ) , ms . keys , ms . values , ms . pending , ms . n ) <EOL> @ wrap <EOL> def LT ( a , b ) : <EOL> """<STR_LIT>""" <EOL> return a < b <EOL> @ wrap <EOL> def binarysort ( keys , values , lo , hi , start ) : <EOL> """<STR_LIT>""" <EOL> assert lo <= start and start <= hi <EOL> _has_values = has_values ( keys , values ) <EOL> if lo == start : <EOL> start += <NUM_LIT:1> <EOL> while start < hi : <EOL> pivot = keys [ start ] <EOL> l = lo <EOL> r = start <EOL> while l < r : <EOL> p = l + ( ( r - l ) >> <NUM_LIT:1> ) <EOL> if LT ( pivot , keys [ p ] ) : <EOL> r = p <EOL> else : <EOL> l = p + <NUM_LIT:1> <EOL> for p in range ( start , l , - <NUM_LIT:1> ) : <EOL> keys [ p ] = keys [ p - <NUM_LIT:1> ] <EOL> keys [ l ] = pivot <EOL> if _has_values : <EOL> pivot_val = values [ start ] <EOL> for p in range ( start , l , - <NUM_LIT:1> ) : <EOL> values [ p ] = values [ p - <NUM_LIT:1> ] <EOL> values [ l ] = pivot_val <EOL> start += <NUM_LIT:1> <EOL> @ wrap <EOL> def count_run ( keys , lo , hi ) : <EOL> """<STR_LIT>""" <EOL> assert lo < hi <EOL> if lo + <NUM_LIT:1> == hi : <EOL> return <NUM_LIT:1> , False <EOL> if LT ( keys [ lo + <NUM_LIT:1> ] , keys [ lo ] ) : <EOL> for k in range ( lo + <NUM_LIT:2> , hi ) : <EOL> if not LT ( keys [ k ] , keys [ k - <NUM_LIT:1> ] ) : <EOL> return k - lo , True <EOL> return hi - lo , True <EOL> else : <EOL> for k in range ( lo + <NUM_LIT:2> , hi ) : <EOL> if LT ( keys [ k ] , keys [ k - <NUM_LIT:1> ] ) : <EOL> return k - lo , False <EOL> return hi - lo , False <EOL> @ wrap <EOL> def gallop_left ( key , a , start , stop , hint ) : <EOL> """<STR_LIT>""" <EOL> assert stop > start <EOL> assert hint >= start and hint < stop <EOL> n = stop - start <EOL> lastofs = <NUM_LIT:0> <EOL> ofs = <NUM_LIT:1> <EOL> if LT ( a [ hint ] , key ) : <EOL> maxofs = stop - hint <EOL> while ofs < maxofs : <EOL> if LT ( a [ hint + ofs ] , key ) : <EOL> lastofs = ofs <EOL> ofs = ( ofs << <NUM_LIT:1> ) + <NUM_LIT:1> <EOL> if ofs <= <NUM_LIT:0> : <EOL> ofs = maxofs <EOL> else : <EOL> break <EOL> if ofs > maxofs : <EOL> ofs = maxofs <EOL> lastofs += hint <EOL> ofs += hint <EOL> else : <EOL> maxofs = hint - start + <NUM_LIT:1> <EOL> while ofs < maxofs : <EOL> if LT ( a [ hint - ofs ] , key ) : <EOL> break <EOL> else : <EOL> lastofs = ofs <EOL> ofs = ( ofs << <NUM_LIT:1> ) + <NUM_LIT:1> <EOL> if ofs <= <NUM_LIT:0> : <EOL> ofs = maxofs <EOL> if ofs > maxofs : <EOL> ofs = maxofs <EOL> lastofs , ofs = hint - ofs , hint - lastofs <EOL> assert start - <NUM_LIT:1> <= lastofs and lastofs < ofs and ofs <= stop <EOL> lastofs += <NUM_LIT:1> <EOL> while lastofs < ofs : <EOL> m = lastofs + ( ( ofs - lastofs ) >> <NUM_LIT:1> ) <EOL> if LT ( a [ m ] , key ) : <EOL> lastofs = m + <NUM_LIT:1> <EOL> else : <EOL> ofs = m <EOL> return ofs <EOL> @ wrap <EOL> def gallop_right ( key , a , start , stop , hint ) : <EOL> """<STR_LIT>""" <EOL> assert stop > start <EOL> assert hint >= start and hint < stop <EOL> n = stop - start <EOL> lastofs = <NUM_LIT:0> <EOL> ofs = <NUM_LIT:1> <EOL> if LT ( key , a [ hint ] ) : <EOL> maxofs = hint - start + <NUM_LIT:1> <EOL> while ofs < maxofs : <EOL> if LT ( key , a [ hint - ofs ] ) : <EOL> lastofs = ofs <EOL> ofs = ( ofs << <NUM_LIT:1> ) + <NUM_LIT:1> <EOL> if ofs <= <NUM_LIT:0> : <EOL> ofs = maxofs <EOL> else : <EOL> break <EOL> if ofs > maxofs : <EOL> ofs = maxofs <EOL> lastofs , ofs = hint - ofs , hint - lastofs <EOL> else : <EOL> maxofs = stop - hint <EOL> while ofs < maxofs : <EOL> if LT ( key , a [ hint + ofs ] ) : <EOL> break <EOL> else : <EOL> lastofs = ofs <EOL> ofs = ( ofs << <NUM_LIT:1> ) + <NUM_LIT:1> <EOL> if ofs <= <NUM_LIT:0> : <EOL> ofs = maxofs <EOL> if ofs > maxofs : <EOL> ofs = maxofs <EOL> lastofs += hint <EOL> ofs += hint <EOL> assert start - <NUM_LIT:1> <= lastofs and lastofs < ofs and ofs <= stop <EOL> lastofs += <NUM_LIT:1> <EOL> while lastofs < ofs : <EOL> m = lastofs + ( ( ofs - lastofs ) >> <NUM_LIT:1> ) <EOL> if LT ( key , a [ m ] ) : <EOL> ofs = m <EOL> else : <EOL> lastofs = m + <NUM_LIT:1> <EOL> return ofs <EOL> @ wrap <EOL> def merge_compute_minrun ( n ) : <EOL> """<STR_LIT>""" <EOL> r = <NUM_LIT:0> <EOL> assert n >= <NUM_LIT:0> <EOL> while n >= <NUM_LIT:64> : <EOL> r |= n & <NUM_LIT:1> <EOL> n >>= <NUM_LIT:1> <EOL> return n + r <EOL> @ wrap <EOL> def sortslice_copy ( dest_keys , dest_values , dest_start , <EOL> src_keys , src_values , src_start , <EOL> nitems ) : <EOL> """<STR_LIT>""" <EOL> assert src_start >= <NUM_LIT:0> <EOL> assert dest_start >= <NUM_LIT:0> <EOL> for i in range ( nitems ) : <EOL> dest_keys [ dest_start + i ] = src_keys [ src_start + i ] <EOL> if has_values ( src_keys , src_values ) : <EOL> for i in range ( nitems ) : <EOL> dest_values [ dest_start + i ] = src_values [ src_start + i ] <EOL> @ wrap <EOL> def sortslice_copy_down ( dest_keys , dest_values , dest_start , <EOL> src_keys , src_values , src_start , <EOL> nitems ) : <EOL> """<STR_LIT>""" <EOL> assert src_start >= <NUM_LIT:0> <EOL> assert dest_start >= <NUM_LIT:0> <EOL> for i in range ( nitems ) : <EOL> dest_keys [ dest_start - i ] = src_keys [ src_start - i ] <EOL> if has_values ( src_keys , src_values ) : <EOL> for i in range ( nitems ) : <EOL> dest_values [ dest_start - i ] = src_values [ src_start - i ] <EOL> DO_GALLOP = <NUM_LIT:1> <EOL> @ wrap <EOL> def merge_lo ( ms , keys , values , ssa , na , ssb , nb ) : <EOL> """<STR_LIT>""" <EOL> assert na > <NUM_LIT:0> and nb > <NUM_LIT:0> and na <= nb <EOL> assert ssb == ssa + na <EOL> ms = merge_getmem ( ms , na ) <EOL> sortslice_copy ( ms . keys , ms . values , <NUM_LIT:0> , <EOL> keys , values , ssa , <EOL> na ) <EOL> a_keys = ms . keys <EOL> a_values = ms . values <EOL> b_keys = keys <EOL> b_values = values <EOL> dest = ssa <EOL> ssa = <NUM_LIT:0> <EOL> _has_values = has_values ( a_keys , a_values ) <EOL> min_gallop = ms . min_gallop <EOL> while nb > <NUM_LIT:0> and na > <NUM_LIT:0> : <EOL> acount = <NUM_LIT:0> <EOL> bcount = <NUM_LIT:0> <EOL> while True : <EOL> if LT ( b_keys [ ssb ] , a_keys [ ssa ] ) : <EOL> keys [ dest ] = b_keys [ ssb ] <EOL> if _has_values : <EOL> values [ dest ] = b_values [ ssb ] <EOL> dest += <NUM_LIT:1> <EOL> ssb += <NUM_LIT:1> <EOL> nb -= <NUM_LIT:1> <EOL> if nb == <NUM_LIT:0> : <EOL> break <EOL> bcount += <NUM_LIT:1> <EOL> acount = <NUM_LIT:0> <EOL> if bcount >= min_gallop : <EOL> break <EOL> else : <EOL> keys [ dest ] = a_keys [ ssa ] <EOL> if _has_values : <EOL> values [ dest ] = a_values [ ssa ] <EOL> dest += <NUM_LIT:1> <EOL> ssa += <NUM_LIT:1> <EOL> na -= <NUM_LIT:1> <EOL> if na == <NUM_LIT:0> : <EOL> break <EOL> acount += <NUM_LIT:1> <EOL> bcount = <NUM_LIT:0> <EOL> if acount >= min_gallop : <EOL> break <EOL> if DO_GALLOP and na > <NUM_LIT:0> and nb > <NUM_LIT:0> : <EOL> min_gallop += <NUM_LIT:1> <EOL> while acount >= MIN_GALLOP or bcount >= MIN_GALLOP : <EOL> min_gallop -= min_gallop > <NUM_LIT:1> <EOL> k = gallop_right ( b_keys [ ssb ] , a_keys , ssa , ssa + na , ssa ) <EOL> k -= ssa <EOL> acount = k <EOL> if k > <NUM_LIT:0> : <EOL> sortslice_copy ( keys , values , dest , <EOL> a_keys , a_values , ssa , <EOL> k ) <EOL> dest += k <EOL> ssa += k <EOL> na -= k <EOL> if na == <NUM_LIT:0> : <EOL> break <EOL> keys [ dest ] = b_keys [ ssb ] <EOL> if _has_values : <EOL> values [ dest ] = b_values [ ssb ] <EOL> dest += <NUM_LIT:1> <EOL> ssb += <NUM_LIT:1> <EOL> nb -= <NUM_LIT:1> <EOL> if nb == <NUM_LIT:0> : <EOL> break <EOL> k = gallop_left ( a_keys [ ssa ] , b_keys , ssb , ssb + nb , ssb ) <EOL> k -= ssb <EOL> bcount = k <EOL> if k > <NUM_LIT:0> : <EOL> sortslice_copy ( keys , values , dest , <EOL> b_keys , b_values , ssb , <EOL> k ) <EOL> dest += k <EOL> ssb += k <EOL> nb -= k <EOL> if nb == <NUM_LIT:0> : <EOL> break <EOL> keys [ dest ] = a_keys [ ssa ] <EOL> if _has_values : <EOL> values [ dest ] = a_values [ ssa ] <EOL> dest += <NUM_LIT:1> <EOL> ssa += <NUM_LIT:1> <EOL> na -= <NUM_LIT:1> <EOL> if na == <NUM_LIT:0> : <EOL> break <EOL> min_gallop += <NUM_LIT:1> <EOL> if nb == <NUM_LIT:0> : <EOL> sortslice_copy ( keys , values , dest , <EOL> a_keys , a_values , ssa , <EOL> na ) <EOL> else : <EOL> assert na == <NUM_LIT:0> <EOL> assert dest == ssb <EOL> return merge_adjust_gallop ( ms , min_gallop ) <EOL> @ wrap <EOL> def merge_hi ( ms , keys , values , ssa , na , ssb , nb ) : <EOL> """<STR_LIT>""" <EOL> assert na > <NUM_LIT:0> and nb > <NUM_LIT:0> and na >= nb <EOL> assert ssb == ssa + na <EOL> ms = merge_getmem ( ms , nb ) <EOL> sortslice_copy ( ms . keys , ms . values , <NUM_LIT:0> , <EOL> keys , values , ssb , <EOL> nb ) <EOL> a_keys = keys <EOL> a_values = values <EOL> b_keys = ms . keys <EOL> b_values = ms . values <EOL> dest = ssb + nb - <NUM_LIT:1> <EOL> ssb = nb - <NUM_LIT:1> <EOL> ssa = ssa + na - <NUM_LIT:1> <EOL> _has_values = has_values ( b_keys , b_values ) <EOL> min_gallop = ms . min_gallop <EOL> while nb > <NUM_LIT:0> and na > <NUM_LIT:0> : <EOL> acount = <NUM_LIT:0> <EOL> bcount = <NUM_LIT:0> <EOL> while True : <EOL> if LT ( b_keys [ ssb ] , a_keys [ ssa ] ) : <EOL> keys [ dest ] = a_keys [ ssa ] <EOL> if _has_values : <EOL> values [ dest ] = a_values [ ssa ] <EOL> dest -= <NUM_LIT:1> <EOL> ssa -= <NUM_LIT:1> <EOL> na -= <NUM_LIT:1> <EOL> if na == <NUM_LIT:0> : <EOL> break <EOL> acount += <NUM_LIT:1> <EOL> bcount = <NUM_LIT:0> <EOL> if acount >= min_gallop : <EOL> break <EOL> else : <EOL> keys [ dest ] = b_keys [ ssb ] <EOL> if _has_values : <EOL> values [ dest ] = b_values [ ssb ] <EOL> dest -= <NUM_LIT:1> <EOL> ssb -= <NUM_LIT:1> <EOL> nb -= <NUM_LIT:1> <EOL> if nb == <NUM_LIT:0> : <EOL> break <EOL> bcount += <NUM_LIT:1> <EOL> acount = <NUM_LIT:0> <EOL> if bcount >= min_gallop : <EOL> break <EOL> if DO_GALLOP and na > <NUM_LIT:0> and nb > <NUM_LIT:0> : <EOL> min_gallop += <NUM_LIT:1> <EOL> while acount >= MIN_GALLOP or bcount >= MIN_GALLOP : <EOL> min_gallop -= min_gallop > <NUM_LIT:1> <EOL> k = gallop_right ( b_keys [ ssb ] , a_keys , ssa - na + <NUM_LIT:1> , ssa + <NUM_LIT:1> , ssa ) <EOL> k = ssa + <NUM_LIT:1> - k <EOL> acount = k <EOL> if k > <NUM_LIT:0> : <EOL> sortslice_copy_down ( keys , values , dest , <EOL> a_keys , a_values , ssa , <EOL> k ) <EOL> dest -= k <EOL> ssa -= k <EOL> na -= k <EOL> if na == <NUM_LIT:0> : <EOL> break <EOL> keys [ dest ] = b_keys [ ssb ] <EOL> if _has_values : <EOL> values [ dest ] = b_values [ ssb ] <EOL> dest -= <NUM_LIT:1> <EOL> ssb -= <NUM_LIT:1> <EOL> nb -= <NUM_LIT:1> <EOL> if nb == <NUM_LIT:0> : <EOL> break <EOL> k = gallop_left ( a_keys [ ssa ] , b_keys , ssb - nb + <NUM_LIT:1> , ssb + <NUM_LIT:1> , ssb ) <EOL> k = ssb + <NUM_LIT:1> - k <EOL> bcount = k <EOL> if k > <NUM_LIT:0> : <EOL> sortslice_copy_down ( keys , values , dest , <EOL> b_keys , b_values , ssb , <EOL> k ) <EOL> dest -= k <EOL> ssb -= k <EOL> nb -= k <EOL> if nb == <NUM_LIT:0> : <EOL> break <EOL> keys [ dest ] = a_keys [ ssa ] <EOL> if _has_values : <EOL> values [ dest ] = a_values [ ssa ] <EOL> dest -= <NUM_LIT:1> <EOL> ssa -= <NUM_LIT:1> <EOL> na -= <NUM_LIT:1> <EOL> if na == <NUM_LIT:0> : <EOL> break <EOL> min_gallop += <NUM_LIT:1> <EOL> if na == <NUM_LIT:0> : <EOL> sortslice_copy ( keys , values , dest - nb + <NUM_LIT:1> , <EOL> b_keys , b_values , ssb - nb + <NUM_LIT:1> , <EOL> nb ) <EOL> else : <EOL> assert nb == <NUM_LIT:0> <EOL> assert dest == ssa <EOL> return merge_adjust_gallop ( ms , min_gallop ) <EOL> @ wrap <EOL> def merge_at ( ms , keys , values , i ) : <EOL> """<STR_LIT>""" <EOL> n = ms . n <EOL> assert n >= <NUM_LIT:2> <EOL> assert i >= <NUM_LIT:0> <EOL> assert i == n - <NUM_LIT:2> or i == n - <NUM_LIT:3> <EOL> ssa , na = ms . pending [ i ] <EOL> ssb , nb = ms . pending [ i + <NUM_LIT:1> ] <EOL> assert na > <NUM_LIT:0> and nb > <NUM_LIT:0> <EOL> assert ssa + na == ssb <EOL> ms . pending [ i ] = MergeRun ( ssa , na + nb ) <EOL> if i == n - <NUM_LIT:3> : <EOL> ms . pending [ i + <NUM_LIT:1> ] = ms . pending [ i + <NUM_LIT:2> ] <EOL> ms = merge_pop ( ms ) <EOL> k = gallop_right ( keys [ ssb ] , keys , ssa , ssa + na , ssa ) <EOL> na -= k - ssa <EOL> ssa = k <EOL> if na == <NUM_LIT:0> : <EOL> return ms <EOL> k = gallop_left ( keys [ ssa + na - <NUM_LIT:1> ] , keys , ssb , ssb + nb , ssb + nb - <NUM_LIT:1> ) <EOL> nb = k - ssb <EOL> if na <= nb : <EOL> return merge_lo ( ms , keys , values , ssa , na , ssb , nb ) <EOL> else : <EOL> return merge_hi ( ms , keys , values , ssa , na , ssb , nb ) <EOL> @ wrap <EOL> def merge_collapse ( ms , keys , values ) : <EOL> """<STR_LIT>""" <EOL> while ms . n > <NUM_LIT:1> : <EOL> pending = ms . pending <EOL> n = ms . n - <NUM_LIT:2> <EOL> if ( ( n > <NUM_LIT:0> and pending [ n - <NUM_LIT:1> ] . size <= pending [ n ] . size + pending [ n + <NUM_LIT:1> ] . size ) or <EOL> ( n > <NUM_LIT:1> and pending [ n - <NUM_LIT:2> ] . size <= pending [ n - <NUM_LIT:1> ] . size + pending [ n ] . size ) ) : <EOL> if pending [ n - <NUM_LIT:1> ] . size < pending [ n + <NUM_LIT:1> ] . size : <EOL> n -= <NUM_LIT:1> <EOL> ms = merge_at ( ms , keys , values , n ) <EOL> elif pending [ n ] . size < pending [ n + <NUM_LIT:1> ] . size : <EOL> ms = merge_at ( ms , keys , values , n ) <EOL> else : <EOL> break <EOL> return ms <EOL> @ wrap <EOL> def merge_force_collapse ( ms , keys , values ) : <EOL> """<STR_LIT>""" <EOL> while ms . n > <NUM_LIT:1> : <EOL> pending = ms . pending <EOL> n = ms . n - <NUM_LIT:2> <EOL> if n > <NUM_LIT:0> : <EOL> if pending [ n - <NUM_LIT:1> ] . size < pending [ n + <NUM_LIT:1> ] . size : <EOL> n -= <NUM_LIT:1> <EOL> ms = merge_at ( ms , keys , values , n ) <EOL> return ms <EOL> @ wrap <EOL> def reverse_slice ( keys , values , start , stop ) : <EOL> """<STR_LIT>""" <EOL> i = start <EOL> j = stop - <NUM_LIT:1> <EOL> while i < j : <EOL> keys [ i ] , keys [ j ] = keys [ j ] , keys [ i ] <EOL> i += <NUM_LIT:1> <EOL> j -= <NUM_LIT:1> <EOL> if has_values ( keys , values ) : <EOL> i = start <EOL> j = stop - <NUM_LIT:1> <EOL> while i < j : <EOL> values [ i ] , values [ j ] = values [ j ] , values [ i ] <EOL> i += <NUM_LIT:1> <EOL> j -= <NUM_LIT:1> <EOL> @ wrap <EOL> def run_timsort_with_mergestate ( ms , keys , values ) : <EOL> """<STR_LIT>""" <EOL> nremaining = len ( keys ) <EOL> if nremaining < <NUM_LIT:2> : <EOL> return <EOL> minrun = merge_compute_minrun ( nremaining ) <EOL> lo = zero <EOL> while nremaining > <NUM_LIT:0> : <EOL> n , desc = count_run ( keys , lo , lo + nremaining ) <EOL> if desc : <EOL> reverse_slice ( keys , values , lo , lo + n ) <EOL> if n < minrun : <EOL> force = min ( minrun , nremaining ) <EOL> binarysort ( keys , values , lo , lo + force , lo + n ) <EOL> n = force <EOL> ms = merge_append ( ms , MergeRun ( lo , n ) ) <EOL> ms = merge_collapse ( ms , keys , values ) <EOL> lo += n <EOL> nremaining -= n <EOL> ms = merge_force_collapse ( ms , keys , values ) <EOL> assert ms . n == <NUM_LIT:1> <EOL> assert ms . pending [ <NUM_LIT:0> ] == ( <NUM_LIT:0> , len ( keys ) ) <EOL> @ wrap <EOL> def run_timsort ( keys ) : <EOL> """<STR_LIT>""" <EOL> values = keys <EOL> run_timsort_with_mergestate ( merge_init ( keys ) , keys , values ) <EOL> @ wrap <EOL> def run_timsort_with_values ( keys , values ) : <EOL> """<STR_LIT>""" <EOL> run_timsort_with_mergestate ( merge_init_with_values ( keys , values ) , <EOL> keys , values ) <EOL> return TimsortImplementation ( <EOL> wrap , <EOL> count_run , binarysort , gallop_left , gallop_right , <EOL> merge_init , merge_append , merge_pop , <EOL> merge_compute_minrun , merge_lo , merge_hi , merge_at , <EOL> merge_force_collapse , merge_collapse , <EOL> run_timsort , run_timsort_with_values ) <EOL> def make_py_timsort ( * args ) : <EOL> return make_timsort_impl ( ( lambda f : f ) , * args ) <EOL> def make_jit_timsort ( * args ) : <EOL> from numba import jit <EOL> return make_timsort_impl ( ( lambda f : jit ( nopython = True ) ( f ) ) , <EOL> * args ) </s>
