$("#ray_8956").html("\n
1<\/a>
2<\/a>
3<\/a>
4<\/a>
5<\/a>
6<\/a>
7<\/a>
8<\/a>
9<\/a>
10<\/a><\/strong>
11<\/a>
12<\/a>
13<\/a>
14<\/a>
15<\/a>
16<\/a>
17<\/a>
18<\/a>
19<\/a>
20<\/a><\/strong>
21<\/a>
22<\/a>
23<\/a>
24<\/a>
25<\/a>
26<\/a>
27<\/a>
28<\/a>
29<\/a>
30<\/a><\/strong>
31<\/a>
32<\/a>
33<\/a>
34<\/a>
35<\/a>
36<\/a>
37<\/a>
38<\/a>
39<\/a><\/pre><\/td>\n  
#count split inversions via divide and conquer strat<\/span>
<\/span>
<\/span>def<\/span> <\/span>sort_and_count<\/span>(<\/span>array<\/span>)<\/span>
<\/span>  <\/span>mid<\/span> <\/span>=<\/span> <\/span>array<\/span>.<\/span>length<\/span> <\/span>/<\/span> <\/span>2<\/span>
<\/span>  <\/span>left<\/span> <\/span>=<\/span> <\/span>array<\/span>[<\/span>0<\/span>...<\/span>mid<\/span>]<\/span>
<\/span>  <\/span>right<\/span> <\/span>=<\/span> <\/span>array<\/span>[<\/span>mid<\/span>..<\/span>-1<\/span>]<\/span>
<\/span>  <\/span>
<\/span>  <\/span>if<\/span> <\/span>array<\/span>.<\/span>count<\/span> <\/span><=<\/span> <\/span>1<\/span>
<\/span>    <\/span>return<\/span> <\/span>0<\/span>,<\/span> <\/span>array<\/span>
<\/span>  <\/span>else<\/span>
<\/span>    <\/span>x<\/span>,<\/span> <\/span>first_sorted_array<\/span> <\/span>=<\/span> <\/span>sort_and_count<\/span>(<\/span>left<\/span>)<\/span>
<\/span>    <\/span>y<\/span>,<\/span> <\/span>second_sorted_array<\/span> <\/span>=<\/span> <\/span>sort_and_count<\/span>(<\/span>right<\/span>)<\/span>
<\/span>    <\/span>z<\/span>,<\/span> <\/span>merged_array<\/span> <\/span>=<\/span> <\/span>merge_and_count_split_inv<\/span>(<\/span>first_sorted_array<\/span>,<\/span>second_sorted_array<\/span>)<\/span>
<\/span>  <\/span>end<\/span>
<\/span>  <\/span>
<\/span>  <\/span>return<\/span> <\/span>x<\/span> <\/span>+<\/span> <\/span>y<\/span> <\/span>+<\/span> <\/span>z<\/span>,<\/span> <\/span>merged_array<\/span>
<\/span>end<\/span>
<\/span>
<\/span>def<\/span> <\/span>merge_and_count_split_inv<\/span>(<\/span>left<\/span>,<\/span>right<\/span>)<\/span>
<\/span>  <\/span>merged_array<\/span> <\/span>=<\/span> <\/span>[<\/span>]<\/span>
<\/span>  <\/span>split_inv<\/span> <\/span>=<\/span> <\/span>0<\/span>  <\/span>
<\/span>  <\/span>
<\/span>  <\/span>while<\/span> <\/span>left<\/span>.<\/span>size<\/span> <\/span>><\/span> <\/span>1<\/span> <\/span>&<\/span> <\/span>right<\/span>.<\/span>size<\/span> <\/span>><\/span> <\/span>1<\/span>
<\/span>    <\/span>if<\/span> <\/span>left<\/span>[<\/span>0<\/span>]<\/span> <\/span><=<\/span> <\/span>right<\/span>[<\/span>0<\/span>]<\/span>
<\/span>      <\/span>merged_array<\/span>.<\/span>push<\/span>(<\/span>left<\/span>.<\/span>shift<\/span>)<\/span>
<\/span>    <\/span>else<\/span> <\/span>if<\/span> <\/span>right<\/span>[<\/span>0<\/span>]<\/span> <\/span><<\/span> <\/span>left<\/span>[<\/span>0<\/span>]<\/span>
<\/span>      <\/span>merged_array<\/span>.<\/span>push<\/span>(<\/span>right<\/span>.<\/span>shift<\/span>)<\/span>
<\/span>      <\/span>split<\/span> <\/span>inv<\/span> <\/span>+=<\/span> <\/span>left<\/span>.<\/span>size<\/span>
<\/span>    <\/span>end<\/span>
<\/span>  <\/span>end<\/span>
<\/span>  <\/span>
<\/span>  <\/span>if<\/span> <\/span>left<\/span>[<\/span>0<\/span>]<\/span>
<\/span>    <\/span>merged_array<\/span>.<\/span>concat<\/span>(<\/span>left<\/span>)<\/span>
<\/span>  <\/span>elsif<\/span> <\/span>right<\/span>[<\/span>0<\/span>]<\/span>
<\/span>    <\/span>merged_array<\/span>.<\/span>concat<\/span>(<\/span>right<\/span>)<\/span>
<\/span>  <\/span>end<\/span>
<\/span>  <\/span>
<\/span>  <\/span>return<\/span> <\/span>split_inv<\/span>,<\/span> <\/span>merged_array<\/span>
<\/span>end<\/span><\/pre><\/td>\n<\/tr><\/table>\n\n");