익명 사용자
로그인하지 않음
토론
기여
계정 만들기
로그인
IT 위키
검색
Merge Sort
편집하기
IT 위키
이름공간
문서
토론
더 보기
더 보기
문서 행위
읽기
편집
원본 편집
역사
경고:
로그인하지 않았습니다. 편집을 하면 IP 주소가 공개되게 됩니다.
로그인
하거나
계정을 생성하면
편집자가 사용자 이름으로 기록되고, 다른 장점도 있습니다.
스팸 방지 검사입니다. 이것을 입력하지
마세요
!
고급
특수 문자
도움말
문단 제목
2단계
3단계
4단계
5단계
형식
넣기
라틴 문자
확장 라틴 문자
IPA 문자
기호
그리스 문자
그리스어 확장
키릴 문자
아랍 문자
아랍어 확장
히브리 문자
뱅골어
타밀어
텔루구어 문자
싱할라 문자
데바나가리어
구자라트 문자
태국어
라오어
크메르어
캐나다 원주민 언어
룬 문자
Á
á
À
à
Â
â
Ä
ä
Ã
ã
Ǎ
ǎ
Ā
ā
Ă
ă
Ą
ą
Å
å
Ć
ć
Ĉ
ĉ
Ç
ç
Č
č
Ċ
ċ
Đ
đ
Ď
ď
É
é
È
è
Ê
ê
Ë
ë
Ě
ě
Ē
ē
Ĕ
ĕ
Ė
ė
Ę
ę
Ĝ
ĝ
Ģ
ģ
Ğ
ğ
Ġ
ġ
Ĥ
ĥ
Ħ
ħ
Í
í
Ì
ì
Î
î
Ï
ï
Ĩ
ĩ
Ǐ
ǐ
Ī
ī
Ĭ
ĭ
İ
ı
Į
į
Ĵ
ĵ
Ķ
ķ
Ĺ
ĺ
Ļ
ļ
Ľ
ľ
Ł
ł
Ń
ń
Ñ
ñ
Ņ
ņ
Ň
ň
Ó
ó
Ò
ò
Ô
ô
Ö
ö
Õ
õ
Ǒ
ǒ
Ō
ō
Ŏ
ŏ
Ǫ
ǫ
Ő
ő
Ŕ
ŕ
Ŗ
ŗ
Ř
ř
Ś
ś
Ŝ
ŝ
Ş
ş
Š
š
Ș
ș
Ț
ț
Ť
ť
Ú
ú
Ù
ù
Û
û
Ü
ü
Ũ
ũ
Ů
ů
Ǔ
ǔ
Ū
ū
ǖ
ǘ
ǚ
ǜ
Ŭ
ŭ
Ų
ų
Ű
ű
Ŵ
ŵ
Ý
ý
Ŷ
ŷ
Ÿ
ÿ
Ȳ
ȳ
Ź
ź
Ž
ž
Ż
ż
Æ
æ
Ǣ
ǣ
Ø
ø
Œ
œ
ß
Ð
ð
Þ
þ
Ə
ə
서식 지정
링크
문단 제목
목록
파일
각주
토론
설명
입력하는 내용
문서에 나오는 결과
기울임꼴
''기울인 글씨''
기울인 글씨
굵게
'''굵은 글씨'''
굵은 글씨
굵고 기울인 글씨
'''''굵고 기울인 글씨'''''
굵고 기울인 글씨
'''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]] [[Category:Algorithm]]
요약:
IT 위키에서의 모든 기여는 크리에이티브 커먼즈 저작자표시-비영리-동일조건변경허락 라이선스로 배포된다는 점을 유의해 주세요(자세한 내용에 대해서는
IT 위키:저작권
문서를 읽어주세요). 만약 여기에 동의하지 않는다면 문서를 저장하지 말아 주세요.
또한, 직접 작성했거나 퍼블릭 도메인과 같은 자유 문서에서 가져왔다는 것을 보증해야 합니다.
저작권이 있는 내용을 허가 없이 저장하지 마세요!
취소
편집 도움말
(새 창에서 열림)
둘러보기
둘러보기
대문
최근 바뀜
광고
위키 도구
위키 도구
특수 문서 목록
문서 도구
문서 도구
사용자 문서 도구
더 보기
여기를 가리키는 문서
가리키는 글의 최근 바뀜
문서 정보
문서 기록