[JAVA][Python][알고리즘] 병합 알고리즘 ; 머지

Java

// 2개의 정수 배열 합치기 : 2개의 배열은 오름차순으로 정렬되어 있다
// 병합 알고리즘 : 오름차순으로 정렬되어 있는 정수 배열을 하나로 병합
import java.util.Arrays;
public class App {
    public static void main(String[] args) throws Exception {
        //[1] Input
        int[] first = {1,3,5};
        int[] second = {2,4,6};
        int M = first.length;
        int N = second.length; // M : N 관행
        int[] merge = new int[N+M];
        int i = 0; int j=0; int k = 0; //i,j,k 관행
        

        //[2] Process : Merge
        while(i< M && j<M){ //둘중하나라도배열의끝에도달할 때까지
            if(first[i]<second[j]){
                merge[k++] = first[i++];
            } else {
                merge[k++] = second[j++];
            }
        }
        while(i< M){
            merge[k++] = first[i++];
        }
        while(j<M){
            merge[k++] = second[j++];
        }

        //[3] Output
        for(int item :merge) {
            System.out.print(item+ " ");
        }
        System.out.println();

    }
}

Python

# [1] Input
first = [1, 3, 5]
second = [2, 4]
M = len(first)
N = len(second)
merge = [0] * (M + N)
i = 0;
j = 0;
k = 0;
# [2] Process
while i < M and j < N:
    if first[i] < second[j]:
        merge[k] = first[i];
        k += 1;
        i += 1
    else:
        merge[k] = second[j];
        k += 1;
        j += 1

while i < M:
    merge[k] = first[i]
    k += 1
    i += 1
while i < N:
    merge[k] = second[j]
    k += 1
    j += 1

# [3] Output
for item in merge:
    print(item, end = ", ")
print()