Matsushita's Blog

Merge Sort

Merge Sort: Counting Inversions in HackerRank

問題 Int型の配列が与えられ、ソートするために必要なスワップの数をカウントするという問題 解き方 O(N2)の解法 この解法はバブルソートの要領で解く。 forループを2重にしてiを0 ≦ i < arr.length, jをi+1 ≦ j < arr.lengthのようにル…

Merge two sorted arrays

Problem You are given two sorted arrays, A and B, where A has large enough buffer at the end to hold B. Write a method to merge B into A in sorted order How to Solve By merging two arrays like merge sort, we can achieve the goal. Since A h…

Merge Sort and Quick Sort

Merge Sort Runtime: 0(n Log(n)) average and worst case. Quick Sort Runtime: 0(n Log(n)) average,0(n2) worst case.