Merge Sort 편집하기

'''Merge Sort''' is a divide-and-conquer sorting algorithm that recursively splits an array into smaller subarrays, sorts them, and then merges the sorted subarrays to produce the final sorted array. It guarantees a worst-case time complexity of O(n log n).
==Algorithm Overview==
Merge Sort follows these steps:
#'''Divide:''' Recursively split the array into two halves until each subarray has one element.
#'''Conquer:''' Sort the subarrays (trivial for single-element arrays).
#'''Merge:''' Combine the sorted subarrays into a single sorted array.
==Example==
Sorting [38, 27, 43, 3, 9, 82, 10] using Merge Sort:
#Split: [38, 27, 43, 3] and [9, 82, 10]
#Split further: [38, 27], [43, 3], [9, 82], [10]
#Base case: Single elements remain → Merge back:
#*Merge [38] and [27] → [27, 38]
#*Merge [43] and [3] → [3, 43]
#*Merge [9] and [82] → [9, 82]
#*Merge [27, 38] and [3, 43] → [3, 27, 38, 43]
#*Merge [9, 82] and [10] → [9, 10, 82]
#*Merge [3, 27, 38, 43] and [9, 10, 82] → [3, 9, 10, 27, 38, 43, 82]
==Implementation==
A simple implementation of Merge Sort in Python:<syntaxhighlight lang="python">
def merge_sort(arr):
    if len(arr) <= 1:
        return arr
    mid = len(arr) // 2
    left = merge_sort(arr[:mid])
    right = merge_sort(arr[mid:])
    return merge(left, right)

def merge(left, right):
    sorted_list = []
    i = j = 0
    while i < len(left) and j < len(right):
        if left[i] < right[j]:
            sorted_list.append(left[i])
            i += 1
        else:
            sorted_list.append(right[j])
            j += 1
    sorted_list.extend(left[i:])
    sorted_list.extend(right[j:])
    return sorted_list

arr = [38, 27, 43, 3, 9, 82, 10]
print(merge_sort(arr))
</syntaxhighlight>
==Time Complexity==
Merge Sort has a time complexity of:
*'''Best case:''' O(n log n) (Even if already sorted, it still splits and merges)
*'''Average case:''' O(n log n)
*'''Worst case:''' O(n log n) (Fully reversed array)
==Space Complexity==
*O(n) – Requires additional space to store subarrays during merging.
==Comparison with Other Sorting Algorithms==
{| class="wikitable"
!Algorithm!!Time Complexity (Worst)!!Space Complexity!!Stable!!In-Place
|-
|Merge Sort||O(n log n)||O(n)||Yes||No
|-
|Quick Sort||O(n²)||O(log n)||No||Yes
|-
|Bubble Sort||O(n²)||O(1)||Yes||Yes
|-
|Heap Sort||O(n log n)||O(1)||No||Yes
|}
==Advantages==
*'''Stable Sorting Algorithm:''' Maintains relative order of equal elements.
*'''Guaranteed O(n log n) Complexity:''' Unlike Quick Sort, it does not degrade to O(n²).
*'''Efficient for Linked Lists:''' Unlike array-based sorting, linked lists benefit from its merging process.
==Limitations==
*'''Not In-Place:''' Requires additional memory for merging subarrays.
*'''Slower for Small Datasets:''' Algorithms like Insertion Sort can be faster for small n.
==Applications==
*Sorting large datasets where stability is required.
*External sorting when data is too large to fit into memory.
*Merging linked lists efficiently.
==See Also==
*[[Sorting Algorithm]]
*[[Quick Sort]]
*[[Heap Sort]]
*[[Divide-and-Conquer Algorithm]]
*[[Time Complexity]]
*[[Stable Sorting]]
[[분류:Algoritm]]