1. s <= e로 할 경우 s == e인 경우 mid는 s와 같아집니다. 그래서 Partition(s, mid)가 재귀호출될 때 다시 s == e가 되고, 그 안에서 다시 Partition(s, mid)가 호출되고... 를 무한히 반복해서 재귀스택이 무한히 쌓이기 때문에 메모리 초과가 됩니다.
2. s부터 e까지 해야 시간 복잡도가 O(nlogn)이 됩니다. 0부터 시작하면 O(n^2)이 됩니다. 왜 그렇게 되는지는 병합 정렬의 시간 복잡도 분석에 대해 찾아보시기를 추천드립니다.
3. 정렬된 내용을 다시 v에 담아줘야 이후 더 큰 범위를 합칠 때 "이미 정렬된 양 부분을 merge한다"는 로직을 지킬 수 있습니다. 안 그러면 양쪽이 정렬되지 않은 상태에서 merge를 시도하게 됩니다.
shinbian11 3년 전
병합 정렬로 코드를 짜다가 3가지의 의문점이 생겨서 질문을 드립니다. 1개만 답해주셔도 되니 답변 바랍니다 ㅠㅠ
1. Partition 내에서 if 문 조건에 s<=e 를 하면 메모리초과가 나고 s<e 로 해야하는이유가 무엇인가요? 어짜피 partition을 해서 계속 쪼개고 쪼개다 보면 원소가 하나밖에 안 남은 경우(s==e)는 또 쪼갤 필요가 없기 때문인가요? 불필요한 계산을 줄이기 위해서?
2. Merge함수 내에서 마지막에 (44번째 줄) i의 범위를 0부터 k-1까지로 하면 시간초과가 나는 이유가 무엇인가요?
3. 왜 45번째 줄에서, ans배열에서 v배열로 다시 옮겨담나요? 20~43번째 코드를 통해 이미 ans 배열에 오름차순으로 정렬해서 담은 거 아닌가요? 그럼 그냥 ans 배열을 출력해도 답이 되지 않나요?
감사합니다!