정렬을 이야기하기 전에 어떤 데이터들의 집합 중에서 원하는 데이터를 찾는 방법을 생각해 보자.

길이가 10인 배열 안에 1~10까지의 숫자가 무작위 순서로 놓여 있고 여기에서 원하는 숫자를 찾는 문제가 있다. 원하는 숫자를 빨리 찾는 방법은 무엇이 있을까? 가장 간단한 방법은 단순히 하나씩 꺼내서 값을 확인하는 방법이다. 그리고 이를 순차 탐색이라 부른다. 만약 원하는 데이터가 제일 마지막, 즉 위 예에서 10번째 탐색에 데이터가 있었던 경우 총 10회 시도만에 값을 찾을 수 있게 된다. 만약 데이터가 1~65535까지 있는데 마지막에 있었다면 65535번의 시도끝에 원하는 데이터를 찾을 수 있는 것이다.

for i in arr:
    if i == myvalue:
        return "Found!!"

return "not found....."

이 시간복잡도는 Big-O로 표현했을 때 O(n)이 된다.

이번에는 데이터가 순서대로 놓여 있었다고 하자. 이 경우 원하는 숫자를 찾기 위한 가장 빠른 방법은 배열의 중간 인덱스 값을 본 다음, 찾아야 하는 값보다 크다면 아래쪽 인덱스를, 작다면 윗쪽 인덱스를 살펴보면 된다. 이 때도 중간값을 찾아 검색한다면 결국에는 원하는 값을 찾을 수 있을 것이다. 이를 이진 탐색이라고 부른다.

def binarysearch(datalist, myvalue):
    min = 0
    max = len(datalist)

    while True:
        median = (max - min) / 2
        if datalist[median] < myvalue:
            max = median
        elif datalist[median] > myvalue:
            min = median
        else:
            return "found!!"

이 케이스에서의 시간복잡도는 Big-O로 표현한다면 O(log2 n)이 된다. 굉장히 효율적으로 바뀌는데, 이를 그래프로 보면 그 차이를 명확하게 알 수 있다. 시간복잡도가 log이므로 n이 크면 클수록 그 속도가 드라마틱하게 바뀌는데, 만약 정렬된 데이터가 17조 6천억 정도 되는 길이라면 최악의 경우라도 44번만 찾아보면 그 값을 찾을 수 있다.(2^44 = 17592186044416)

그렇다면 데이터를 정렬하는 이슈를 생각해 보자. 위에서 예를 들었지만, 데이터가 17조 정도 되는데 이를 정렬하는 것은 시간이 얼마나 걸릴까? 그리고 이를 효율적으로 정렬하는 방법은 어떤 것이 있을까?