$("#ray_8956").html("
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>
#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>