データベースにおけるソート処理の概要

MySQL などの relational database において、ORDER BY 句を使用した際に索引（index）が利用できない場合、サーバー側でソートアルゴリズムを用いたファイルソートが行われます。この処理は以下の条件によって使い分けられます。

• ソート対象のデータがメモリ上に収まる場合：メモリ内にてクイックソートが適用されます。
• データ量がメモリ容量を超える場合：データを分割してファイルに書き出し、複数のファイルに対してマージソートを実行します。
• LIMIT 句が含まれる場合：全件ソートせず、ヒープソートを用いて必要な件数だけ効率的に取得します。

主要アルゴリズムの計算量比較

代表的なソートアルゴリズムにおける時間計算量、空間計算量、および安定性の比較表を以下に示します。データ規模 n に対する性能評価の基準となります。

パフォーマンスベンチマーク

10 万件の乱数データに対して各アルゴリズムを実行した際の測定結果は以下の通りです。

• バブルソート：約 13,411ms
• マージソート：約 34ms
• クイックソート：約 9ms
• ヒープソート（未最適化）：約 20,248ms
• ヒープソート（最適化後）：約 9ms

この結果から、大規模データにおいてはクイックソートおよび最適化されたヒープソートが顕著に高速であることがわかります。ただし、データの分布状況によってはマージソートの方が安定するケースもあります。

バブルソートの実装

隣接する要素を比較し、必要に応じて交換を繰り返す最も基本的なアルゴリズムです。最大値が順次配列の末尾へ確定していく様子から名付けられています。

package main

import "fmt"

func main() {
    data := []int{45, 145, 245, 32, 5, 2, 69, 239, 12, 40}
    fmt.Println("Before:", data)
    bubbleSort(data)
    fmt.Println("After:", data)
}

func bubbleSort(nums []int) {
    n := len(nums)
    for i := 0; i < n-1; i++ {
        swapped := false
        for j := 0; j < n-i-1; j++ {
            if nums[j] > nums[j+1] {
                nums[j], nums[j+1] = nums[j+1], nums[j]
                swapped = true
            }
        }
        // 交換が発生しなければ終了
        if !swapped {
            break
        }
    }
}

クイックソートの実装

基準値（ピボット）を選び、それより小さい要素を左側、大きい要素を右側に分割する操作を再帰的に繰り返します。平均的に非常に高速な処理が期待できます。

package main

import "fmt"

func main() {
    vals := []int{45, 145, 245, 32, 5, 2, 69, 239, 12, 40}
    fmt.Println("Before:", vals)
    quickSort(vals, 0, len(vals)-1)
    fmt.Println("After:", vals)
}

func quickSort(arr []int, low, high int) {
    if low < high {
        p := partition(arr, low, high)
        quickSort(arr, low, p-1)
        quickSort(arr, p+1, high)
    }
}

func partition(arr []int, low, high int) int {
    pivot := arr[high]
    i := low - 1
    for j := low; j < high; j++ {
        if arr[j] <= pivot {
            i++
            arr[i], arr[j] = arr[j], arr[i]
        }
    }
    arr[i+1], arr[high] = arr[high], arr[i+1]
    return i + 1
}

マージソートの実装

配列を半分ずつに分割し、それぞれをソートした後に統合（マージ）する手法です。再帰的な実装が一般的で、安定ソートとして知られています。

package main

import "fmt"

func main() {
    sequence := []int{45, 145, 245, 32, 5, 2, 69, 239, 12, 40}
    fmt.Println("Before:", sequence)
    mergeSort(sequence)
    fmt.Println("After:", sequence)
}

func mergeSort(arr []int) {
    if len(arr) <= 1 {
        return
    }
    mid := len(arr) / 2
    left := arr[:mid]
    right := arr[mid:]

    mergeSort(left)
    mergeSort(right)

    merge(arr, left, right)
}

func merge(result, left, right []int) {
    i, j, k := 0, 0, 0
    for i < len(left) && j < len(right) {
        if left[i] <= right[j] {
            result[k] = left[i]
            i++
        } else {
            result[k] = right[j]
            j++
        }
        k++
    }
    for i < len(left) {
        result[k] = left[i]
        i++
        k++
    }
    for j < len(right) {
        result[k] = right[j]
        j++
        k++
    }
}

ヒープソートの実装

二分ヒープ構造を利用したソートです。まず配列を最大ヒープ（または最小ヒープ）に変換し、ルート要素を末尾と交換しながら_heapify_ を繰り返すことで整列を行います。追加メモリをほとんど必要としません。

package main

import "fmt"

func main() {
    items := []int{45, 145, 245, 32, 5, 2, 69, 239, 12, 40}
    fmt.Println("Before:", items)
    heapSort(items)
    fmt.Println("After:", items)
}

func heapSort(arr []int) {
    n := len(arr)
    // ヒープの構築
    for i := n/2 - 1; i >= 0; i-- {
        siftDown(arr, i, n)
    }
    // ソート実行
    for i := n - 1; i > 0; i-- {
        arr[0], arr[i] = arr[i], arr[0]
        siftDown(arr, 0, i)
    }
}

func siftDown(arr []int, root, limit int) {
    for {
        child := 2*root + 1
        if child >= limit {
            break
        }
        // 右の子が存在し、左より大きければ右を選択
        if child+1 < limit && arr[child] < arr[child+1] {
            child++
        }
        // ルートの方が大きければ終了
        if arr[root] >= arr[child] {
            break
        }
        arr[root], arr[child] = arr[child], arr[root]
        root = child
    }
}