결론 부터 말하자면:
    직접 구현하는 머지소트의 성능 향상을 위해서 inplace 머지소트를 권하는 것은 error다.

코세가 높이 치하한 WikiSort:
    O(1) inplace merge 를 사용하는 sort 들.
    https://gall.dcinside.com/board/view/?id=programming&no=949810

//WikiSort, std::stable_sort, std::sort의 속도 비교
WikiSort:
    https://github.com/BonzaiThePenguin/WikiSort/blob/master/WikiSort.cpp
    ==> WikiSort와 std::stable_sort 벤치마크가 포함돼 있어서
        이 파일에 std::sort만 추가시켜서 테스트했다.

결과:
https://wandbox.org/permlink/Z94HpJDwknXCyRbY
//for vector(size_t); random 시퀀스
             |   times(seconds)     |   ratios
           n |   wiki   stable  sort   |   wiki stable sort
    ---------------------------------------------------
      200000|  0.039  0.034  0.034 |   1.14  1.00  1.00
      400000|  0.206  0.078  0.063 |   3.29  1.24  1.00
      600000|  0.144  0.123  0.100 |   1.44  1.23  1.00
      800000|  0.205  0.182  0.149 |   1.38  1.22  1.00
     1000000|  0.256  0.300  0.174 |   1.47  1.73  1.00
     1200000|  0.346  0.412  0.213 |   1.63  1.94  1.00
     1400000|  0.393  0.501  0.260 |   1.51  1.93  1.00
     1600000|  0.455  0.582  0.347 |   1.31  1.68  1.00
     1800000|  0.581  0.742  0.361 |   1.61  2.06  1.00
     2000000|  0.680  0.912  0.385 |   1.77  2.37  1.00
    # Tests completed in 9.82773 seconds
        total |  3.306  3.867  2.085 |   1.59  1.85  1.00


https://wandbox.org/permlink/MLzJahzaXsVozd85
//for vector(size_[3]); random 시퀀스
             |   times(seconds)    |   ratios
           n |   wiki   stable sort   |   wiki stable sort
    ---------------------------------------------------
      200000|  0.075  0.077  0.071 |   1.07  1.09  1.00
      400000|  0.197  0.351  0.123 |   1.60  2.85  1.00
      600000|  0.323  0.664  0.214 |   1.51  3.11  1.00
      800000|  0.440  1.005  0.376 |   1.17  2.67  1.00
     1000000|  0.648  1.489  0.392 |   1.65  3.80  1.00
     1200000|  0.932  1.686  0.594 |   1.57  2.84  1.00
     1400000|  0.994  1.837  0.607 |   1.64  3.03  1.00
     1600000|  0.996  2.121  0.635 |   1.57  3.34  1.00
     1800000|  1.034  2.260  0.739 |   1.40  3.06  1.00
     2000000|  1.113  2.509  0.815 |   1.37  3.08  1.00
    # Tests completed in 29.8015 seconds
         total |  6.752 13.999  4.567 |   1.48  3.07  1.00

note: WikiSort건 std::stable_sort건 많이 느리다(1.59배,1.85배).
    특히 stable_sort는 element복사비용이 증가하면(즉, element 크기가 증가하면) 더 그렇다(3.07배).
    WikiSort, stable_sort가 가끔, std::sort와 비슷하거나 오히려 더 빠르게 나오는 경우도 있다.
    내 컴퓨터에서는 이렇게 까지 심하게 속도차가 나지는 않긴 한데, wandbox에서는 재실행해도 비슷하게 나옴

나도 착각을 한게 있는데, 완성된 함수로 구현된 알고리즘들은 외부 버퍼(O(1) 크기 등)를 사용하는 게 있다는 것을 깜박했었디.
오래전에 봤던 거에다 순수 inplace 머지에만 관심을 뒀었기 때문에 착각하고 과장되거나 부정확하게 언급한 부분이 있었던거 같다.
그러나 적당크기의 외부버퍼를 사용하는 inplace 머지소트도, 코세님 조차 높이 치하하는 잘 짜여진 inplace 머지소트 조차
순수 성능향상을 목적으로 선택하기에는 기본적으로 느리다는 것은 돌려 봤으면 안다는 것은 변함이 없다.


코세야 진짜 "짜보고서 떠든"거 맞어?  거짓말 친거 아니고?