# Insertion Sort Advanced Analysis

# Insertion Sort Advanced Analysis

+ 0 comments For those who attempt to implement Insertion sort, don't. This is the brute force method of what should be done, you only need to find a way to do it in N log N time. This is to actually count the inversions while merge sorting. A hint: when merging two subarrays, when taking an element of the right half, the number of inversions that it has is the number of elements still notm erged from the left half.

`public static long count(int[] a) { long inversions = 0; for (int i = 0; i < a.length; i++) for (int j = i; j < a.length; j++) if (a[i] > a[j]) inversions++; return inversions; }`

+ 1 comment i don't know why this is showing TLE. Can anyone optimise this...

#include <bits/stdc++.h> using namespace std; int insertionSort(int array[], int n) { int count = 0; for(int i = 1; i < n; i++){ int res = array[i]; int j = i-1; while(j>=0 && array[j]>res){ array[j+1] = array[j]; j--; count++; } array[j+1] = res; } return count; } int main() { int t; cin >> t; while(t--){ int n; cin >> n; int array[n]; for(int i = 0; i < n; i++){ cin >> array[i]; } cout << insertionSort(array, n) << endl; } }

+ 0 comments passing the challenge really depens to the enviroment , i have wrote below and did not pass for 2 first submit but in third submit it passed all test cases.

def insertionSort(arr): # Write your code here len_arr = len(arr) if len_arr == 1: return 0 mid = len_arr // 2 n = len_arr - mid left = arr[:mid] right = arr[mid:] answer = insertionSort(left) + insertionSort(right) count_left = 0 count_right = 0 for i in range(len_arr): if count_left < mid and\ (count_right >= n or left[count_left] <= right[count_right]): arr[i] = left[count_left] answer += count_right count_left += 1 elif count_right < n: arr[i] = right[count_right] count_right += 1 return answer

+ 0 comments https://zeroplusfour.com/insertion-sort-advanced-analysis/

Here's how I did in all languages Java 8 , C++ , C , Python 3, Python 2.

+ 1 comment Indeed merge sort with Python under certain conditions does not work. In C++ it works. However, remember to change results to long type, as it can overflow otherwise.

BIT is an interesting approach and having seen the comments here, I will try it now for practce.

Sort 315 Discussions, By:

Please Login in order to post a comment