STL 및 .NET 기본 라이브러리 기본 검색에서 어떤 정렬 알고리즘이 사용됩니까?

Question

나는 이제 실시 된 버전의 Merge 정렬에서 작업하고 있습니다. C ++ 및 C#으로 구현했습니다. 그런 다음 각각 stl sort 및 array.sort () 알고리즘과 비교하십시오. C ++에서는 동일 (때로는 더 나은) 결과를 얻었습니다. 그러나 C#에서는 포인터 사용에 안전하지 않은 코드를 사용해야했습니다. 여기서 성능은 기본 정렬과 그다지 비슷하지 않습니다. 그래서 알고 싶습니다.

1. STL 및 .NET 기본 클래스 라이브러리에서 사용되는 알고리즘은 무엇입니까?
2. 안전하지 않은 코드에 수행 문제가 있습니까?
3. 새로운 알고리즘의 수행을 측정하는 것과 관련하여 저를위한 제안이 있습니까?

Answer 1

.NET은 QuickSort의 변형 (Sedgewick의 3 개의 QuickSort 중앙값)을 사용합니다.

정렬 전문가가 아니라면 광범위한 데이터 (임의, 이미 순서 및 리버스 주문 세트 포함)를 통해 내장형 정렬을 이길 수 있다면 놀랄 것입니다. 안전하지 않은 코드에 의지하는 것은 일반적으로 나쁜 생각입니다 ...

Answer 2

STL 정렬은 구현에 따라 달라질 수 있지만 (Wikipedia가 말한 것처럼) 일반적으로 QuickSort와 Heapsort의 조합 인 IntroTrosort입니다. O (n log n) 비교의 평균 복잡성이 있어야합니다.

Answer 3

.NET은 QuickSort를 사용합니다. 당신이 사용할 수있는 반사기 System.collections.generic.arraysorthelper의 구현을 보려면

대부분의 경우 최악의 실행 시간이 더 길지만 QuickSort는 Mergesort보다 빠르게 실행됩니다. 표준 QuickSort에 대해서도 약간의 개선이 있었지만이 중 하나가 사용되는지 확실하지 않습니다.

나는 QuickSort를 사용하여 STL을 기억하는 것 같지만 완전히 확실하지 않습니다.