정렬된거 합을 정렬하려하는데 O(n^2)만에 됨?

[ㅁㄴㅇㄹ(125.128)]

a1, a2, a3, a4, ... , an
b1, b2, b3, b4, ..., bn
이렇게 n개씩이 정렬되있을때

이렇게 a에서 하나, b에서 하나씩 골라서 더하면 n제곱개가 나오는데
이걸 정렬된걸로 얻으려고 하는데
더한거 다 넣은다음 소트하면 O(n^2logn)이되잖아?
근데 a, b 둘다 정렬되있으니까 혹시 O(n^2)만에 구할 수 있는 방법이 있나 하는데,
있나

[cyber(basad)]

합의 기호 ∑

[에이시아(203.90)]

퀵소트 써 nlgn이야 아니면 합병정렬 nlgn

[ㅁㄴㅇㄹ(125.128)]

뭔 개소리야

[ㅁㄴㅇㄹ(125.128)]

n^2개니까 n^2logn이지

[ㅁㄴㅇㄹ(125.128)]

a1, a2, a3 b1, b2, b3 이렇게 있으면 a1+b1, a1+b2, a1+b3, a2+b1, a2+b2, a2+b3, a3+b1, a3+b2, a3+b3 이걸 정렬된채로 구한다고

[z(192.249)]

a1+b1이 제일 작으니까 쳐넣고, a1+b2랑 a2+b1을 비교해서 작은걸 쳐넣고 큰거는 저장해놓고, a1+b2가 작은거면 a1+b3랑 저장해놓은거랑 비교해서 작은거 쳐넣고 이런식으로 차례대로 해나가면 n^2만에 할수있음.