합병정렬 MergeSort 코틀린 Kotlin 설명x

class mergeSort {
    fun sort(){

        var array = arrayOf(9,41,2,3,1,10,8,6)
       array=  mergeSort(0,array.size-1,array)
        for(i in array.indices){
            println(array[i])
        }
    }

    fun mergeSort(start : Int ,end : Int , array : Array<Int>)  : Array<Int>{
        var arraylist = array
        if(start>=end){
            return arraylist
        }
        var mid = (start+end)/2

        arraylist=mergeSort(start,mid,arraylist)
        arraylist=mergeSort(mid+1,end,arraylist)
        arraylist= merge(start , mid , end , arraylist)
        return arraylist

    }
     fun merge(start : Int, mid : Int, end : Int, array : Array<Int>) : Array<Int>{

        var leftStart = start
        var rightStart = mid+1
        var num = start
        var temp = IntArray(array.size)

        while(true){

                if(array[leftStart]>array[rightStart]){
                    temp[num] = array[rightStart]
                    rightStart++
                    num++
                } else if(array[leftStart]<=array[rightStart]){
                    temp[num] = array[leftStart]
                    num++
                    leftStart++
                }

                if(leftStart>mid){
                    for(i in rightStart..end){
                        temp[num] = array[i]
                        num++
                    }
                    for(i in start..end){
                        array[i] = temp[i]
                    }
                    return array
                }else if(rightStart>end){
                    for(i in leftStart..mid){
                        temp[num] = array[i]
                        num++
                    }
                    for(i in start..end){
                        array[i] = temp[i]
                    }
                    return array
                }
            }
        }
}

 

합병정렬

 

장점 : 다른 정렬에 비해 안정적이고 O(nlogn) 으로 효율적이다 

퀵 정렬은 최악의 경우 O(N제곱) 이 되지만 합병정렬은 최악의 경우에도 O(nlogn)이다

 

단점 : 이미 정렬된 경우에 sort를 진행 할 경우에도 O(nlogn)이다

버블 정렬일 경우에는 O(n)으로 정렬된 경우에는 버블 정렬이 더 효과적이다