gistfile1.txt

import java.util.*;

public class IterativeMergeSort {

    public static Term[] iterativeMergeSort(Term[] terms) {
        if (terms == null || terms.length <= 1) {
            return terms;
        }

        int n = terms.length;
        Term[] temp = new Term[n];

        // 반복문을 사용한 bottom-up 머지소트
        for (int size = 1; size < n; size *= 2) {
            for (int left = 0; left < n; left += 2 * size) {
                int mid = Math.min(left + size - 1, n - 1);
                int right = Math.min(left + 2 * size - 1, n - 1);
                merge(terms, temp, left, mid, right);
            }
        }
        return terms;
    }

    private static void merge(Term[] terms, Term[] temp, int left, int mid, int right) {
        int i = left;    // 왼쪽 부분 배열의 시작 인덱스
        int j = mid + 1; // 오른쪽 부분 배열의 시작 인덱스
        int k = left;    // 병합된 배열의 인덱스

        // 두 부분 배열을 비교하면서 병합
        while (i <= mid && j <= right) {
            if (terms[i].compareTo(terms[j]) <= 0) {
                temp[k++] = terms[i++];
            } else {
                temp[k++] = terms[j++];
            }
        }

        // 왼쪽 부분 배열의 남은 요소들 복사
        while (i <= mid) {
            temp[k++] = terms[i++];
        }

        // 오른쪽 부분 배열의 남은 요소들 복사
        while (j <= right) {
            temp[k++] = terms[j++];
        }

        // 임시 배열의 내용을 원본 배열로 복사
        for (i = left; i <= right; i++) {
            terms[i] = temp[i];
        }
    }

    public static void printTerms(Term[] terms, String message) {
        System.out.print(message);
        for (int i = 0; i < terms.length; i++) {
            System.out.print(terms[i]);
            if (i < terms.length - 1) {
                System.out.print(", ");
            }
        }
        System.out.println();
    }

    public static void main(String[] args) {
        System.out.println("=== Term 클래스를 사용한 반복문 기반 머지소트 테스트 ===");

        // 테스트용 Term 배열 생성
        Term[] testTerms = {new Term(3.0, 2), new Term(1.0, 5), new Term(2.0, 3), new Term(4.0, 1), new Term(5.0, 4), new Term(1.5, 6), new Term(2.5, 0)};

        // 원본 배열 출력
        printTerms(testTerms, "정렬 전: ");

        // 반복문 기반 머지소트 수행
        Term[] sortedTerms = iterativeMergeSort(testTerms.clone());

        // 정렬된 배열 출력
        printTerms(sortedTerms, "정렬 후: ");
    }
}