[C++] C++ sort는 어떤 알고리즘을 사용할까

서론 

 '리스트는 어떤 정렬 알고리즘을 사용하나요?'

 사실 algorithm 헤더에 있는 sort는 어떤 알고리즘을 사용하는가에 대한 이야기는 많이 있었습니다. 그런데 리스트의 경우 리스트 내부 함수로 sort 함수가 있으며 이 함수가 어떤 알고리즘을 채용하는지 알수 없었습니다. 때문에 여기저기 돌아다니면서 얻은 정보를 정리해서 작성해보려고 합니다.

 

 혹시나 더 좋은 정보를 얻으신 분들이 있다면 꼭꼭 댓글로 알려주시면 감사하겠습니다 (_ _)

 

 

 

<algorithm> 헤더에 있는 sort 함수 - 퀵소트, 인트로 소트

 일단 vector 등에 사용할 수 있는 sort 함수의 경우 간단하게 자료들을 구할 수 있었습니다. 그리고 내린 결론은 '이전에는 퀵소트를 사용했지만 현재는 intro sort를 사용하고 있다!' 입니다.

 

 일단 퀵소트의 경우에는 O(nlogn) 의 시간복잡도를 가지지만 상황이 안좋은 경우 O(n^2) 알고리즘을 가지게 된다는 이야기는 유명합니다. 이에 따라서 표준의 sort도 안정적인 시간을 뽑아내주기 위해서 여러 함수를 섞어서 사용하고 있다는 것이죠. 이렇게 제안된 알고리즘이 introsort이고 이는 하이브리드 정렬 알고리즘이라고 불리기도 합니다.

 

 introsort가 사용하는 알고리즘은 퀵소트, 힙소트, 삽입 정렬 입니다. 내부 구현사항은 거의 숨겨져 있어서 사용자가 눈치챌 일은 없지만 일단 배열의 수가 적다면 삽입 정렬을 사용하고 퀵소트를 적용하다가 시간이 오래 걸린다 판단했을 경우 힙소트로 전환해 풀이를 한다고 합니다. 이 과정에서 배열이 나누어지면서 배열 크기가 작아지면 삽입 정렬을 사용하게 된다고 하네요.

---

 이 전환 과정에 대해서는 크게 '이거다!' 할만한 느낌을 받지 못했고 제가 정확히 알지 못했기 때문에 전환 과정에 대해서는 따로 이야기드리지 않겠습니다.

 

 

 

list의 sort는 어떨까?

일단 list의 경우 노드 기반 자료구조기도 하고 algorithm 헤더의 sort가 아닌 멤버 함수인 sort를 사용하기에 더더욱 미스테리입니다.

  template<typename _Tp, typename _Alloc>
    void list<_Tp, _Alloc>::sort()
    {
      // Do nothing if the list has length 0 or 1.
      if (this->_M_impl._M_node._M_next != &this->_M_impl._M_node
	  && this->_M_impl._M_node._M_next->_M_next != &this->_M_impl._M_node)
      {
        list __carry;
        list __tmp[64];
        list * __fill = __tmp;
        list * __counter;

        do
	  {
	    __carry.splice(__carry.begin(), *this, begin());

	    for(__counter = __tmp;
		__counter != __fill && !__counter->empty();
		++__counter)
	      {
		__counter->merge(__carry);
		__carry.swap(*__counter);
	      }
	    __carry.swap(*__counter);
	    if (__counter == __fill)
	      ++__fill;
	  }
	while ( !empty() );

        for (__counter = __tmp + 1; __counter != __fill; ++__counter)
          __counter->merge(*(__counter - 1));
        swap( *(__fill - 1) );
      }
    }

 일단 제가 사용하는 환경에서 list.sort를 보면 이런 코드가 나오게 됩니다. 여기 보면 merge가 등장하는걸 볼 수 있는데 이걸로 볼 수 있듯 list는 머지소트를 사용한다는 것을 알 수 있습니다. 이와 관련한 것들을 찾아보면 mergesort는 stable sort라 채용되었다는 이야기를 찾아보실 수 있습니다.

 

 

 

 참고 자료

Introsort - Wikipedia

 

Which sorting algorithm is used by STL's list::sort()?

 

 

Which sorting algorithm is used by Microsoft's STL::list::sort()?