http://www.ktug.org/xe/index.php?document_srl=246410&mid=KTUG_QnA_board 에서 제시된 솔루션을 분석하다가 \clist_sort:Nn이 어떤 정렬 알고리즘을 사용할까 궁금해졌습니다.

\clist_sort:Nn \l_foo_clist {
\int_compare:nNnTF { #1 } > { #2 }
{ \sort_return_swapped: }
{ \sort_return_same: } }

이것은 단지 오름차순으로 할지 내림차순으로 할지 지정하는 것이기 때문에 내부에서 어떻게 돌아가는지 알 수 없죠.

찾아보니, bubble, insertion, merge, quicksort 알고리즘이 있는가 봅니다. \clist_sort:Nn은, 근거는 없지만, bubble 아니면 insertion을 사용할 것 같습니다. bubble과 insertion은 유사한데 bubble은 뒤쪽부터 정렬되게 하고, insertion은 앞쪽부터 정렬되게 하는 것으로 이해했습니다. merge와 quicksort는 쪼갰다가 합치는 것인데, quicksort는 이름과 달리 그닥 빠른 것 같지도 않습니다. 

아무튼 텍에서 sort 같은 고급(?) 함수가 제공된다는 것이 놀랍습니다. 

웹을 뒤져서 구한 파이썬 코드로 이렇게 해봤습니다. merge 알고리즘에서는 merge 함수가 요체인 듯하여, 실은 꼼수 같은 느낌이 들어서, 제외했습니다.

bubble이 이해하기도 쉽고, 데이터가 다르면 결과가 달라질지 모르겠지만, 저 정렬 처리를 1000번 반복하는 데에 0.0026 초로 가장 빨랐습니다.

import timeit
from random import randint

list = [8, 2, 6, 4, 5, 5, 7, 2, 3, 9, 1, 0, 2, 7, 6]

def bubble_sort(array=list):
    n = len(array)
    for i in range(n):
        already_sorted = True
        for j in range(n - i - 1):
            if array[j] > array[j + 1]:
                array[j], array[j + 1] = array[j + 1], array[j]
                already_sorted = False
        if already_sorted:
            break
    return array

def insertion_sort(array=list):
    for i in range(1, len(array)):
        key_item = array[i]
        j = i - 1
        while j >= 0 and array[j] > key_item:
            array[j + 1] = array[j]
            j -= 1
        array[j + 1] = key_item
    return array

def quicksort(array=list):
    if len(array) < 2:
        return array
    low, same, high = [], [], []
    pivot = array[randint(0, len(array) - 1)]
    for item in array:
        if item < pivot:
            low.append(item)
        elif item == pivot:
            same.append(item)
        elif item > pivot:
            high.append(item)
    return quicksort(low) + same + quicksort(high)

print(list)
print('bubble', bubble_sort(), timeit.timeit(bubble_sort, number=1000))
print('insertion', insertion_sort(), timeit.timeit(insertion_sort, number=1000))
print('quicksort', quicksort(), timeit.timeit(quicksort, number=1000))