어떤 종류의 정렬입니까? 실행 시간은 어떻게됩니까?

Question

나는 어떤 종류의 정렬이 아래의 정렬인지, 그리고 큰 O 표기법에서의 실행 시간은 어떨까 궁금합니다. 내 친구는 알고리즘에 대한 지식없이이 정렬 함수를 작성했으며 이제 우리는 얼마나 빨리/효율적으로 메모리가 효율적인지에 관해 논쟁 중입니다. 그러니 제발요, 분석을 도와주세요.

void sort(int* a, int size) 
{ 
    if (size <= 1) return; 
    else if (size == 2) 
    { 
     if (a[0] > a[1]) 
      swap (a[0], a[1]); 
     return; 
    } 
    else 
    { 
     int i = size/2; 
     sort(a, i); 
     sort(a+i, size - i); 
     int j = 0, k = i ; 
     while (k < size && j < k) 
     { 
      if (a[j] > a[k]) 
      { 
       int temp = k; 
       while (temp > j) 
       { 
        swap(a[temp - 1], a[temp]); 
        temp--; 
       } 
       k++; 
      } 
      j++; 
     } 
    } 
} 

은 머지 소트 기본적으로 사용자들은

Answer 1

을 :) 감사하지만, N^2-장소 병합 단계로. mergesort를 분석하는 것처럼 표준 수학을 수행하면 n^2 실행 시간이 있음을 발견해야합니다. 이를 수행하기 위해 풀어야 할 관련 방정식은 f(n) = n^2 + 2f(n/2)입니다.