mergesort.go

mergesort.go

package main

import (
	"fmt"
)

var inversion int
func merge(arr []int, low, mid,high int){
  
leftarr:=make([]int,mid-low+1)
rightarr:=make([]int,high-mid)
for i:=0;i<mid-low+1;i++{
	leftarr[i] = arr[low+i]
}
for i:=0;i<high-mid;i++{
	rightarr[i] = arr[mid+1+i]
}
i,j,k:=0, 0,low
for ; i<mid-low+1 && j<high-mid && k<high;k++{
fmt.Println(leftarr,rightarr,arr)
	if leftarr[i]>rightarr[j]{
	fmt.Println("inversion",inversion)
	inversion++
	arr[k]=rightarr[j]
	j++
	}else{
	arr[k]=leftarr[i]
	i++
	}
}
fmt.Println(i,low,j,mid,k,high)
for ;i<mid-low+1;i++{
	arr[k]=leftarr[i]
	k++
	}

for ;j<high-mid ;j++{
	arr[k]=rightarr[j]
	k++
	}

	
}

func mergeSort(arr []int, begin,end int){
	if begin>=end {
		return 
	}
	 mid := begin + (end - begin) / 2;
    mergeSort(arr[:], begin, mid);
    mergeSort(arr[:], mid + 1, end);
    merge(arr[:], begin, mid, end);
}
	
	

func main() {
	arr :=[]int{4,2,8,3,9,1}

	mergeSort(arr[:],0,5)
	fmt.Println(arr)
	fmt.Println(inversion)
}