[Sorting] Merge Sort 합병 정렬

Merging is the operation of combining two sorted files to make one larger sorted file.

 

Merge Sort applies the "divide-and-conquer" paradigm as Quick Sort does. In Merge Sort, two recursive calls were followed by a merging procedure, which could be described as follows:

1. Divide the file in half
2. Sort the two halves recursively
3. Merge the two halves together while sorting them

Merge Sort is preferred over Quick Sort when there is a large dataset, and/or stored in external storage!

2021.08.24 - [Algorithms] - [Sorting] Quick Sort 퀵 정렬

 

# Example

 

# Pseudocode

mid: midpoint of the array

arr: original array
L: left-side array
R: right-side array
n1: left-side array size
n2: right-side array size

merge_sort(left, right):
	if left > right
    	return
    m := left + (right - 1) / 2;
    
    merge_sort(left, mid);
    merge_sort(mid + 1, right);
    
    merge(left, mid, right);
end

merge(left, mid, right):
    /* initialise both array sizes */
    n1 := mid - l + 1
    n2 := r - m
    
    /* Assign size to arrays each */
    L.resize(n1);
    R.resize(n2);
    
    /* insert values to L array */
    for i is 0 to n1 - 1 do:
    	L[i] := arr[l + i]
    end for
    
    /* insert values to R array */
    for j is 0 to n2 - 1 do:
    	R[j] := arr[m + 1 + j]
    end for
    
    /* initialise variables */
    i := 0
    j := 0
    k := l
    
    /* arrange values in ascending */
    while i < n1 and j < n2 do:
    	if L[i] <= R[j]
        	arr[k] := L[i++]
        else
        	arr[k] := R[j++]
        
        /* increase k by 1 */
        k++
    end while
    
    /* insert the rest of values in left array */
    while i < n1 do:
    	arr[k++] := L[i++]
    end while
        
    /* insert the rest of values in right array */
    while j < n2 do:
    	arr[k++] := R[j++]
    end while

 

# Computation in C

# Time Complexity

• Worst complexity: n*log(n)
• Average complexity: n*log(n)
• Best complexity: n*log(n)
• Space complexity: n

Merge Sort can always run in O(N log N) time, so this method is stable and simple to implement :)