best case O(n log n) but bigger constant than quick sort
https://en.wikipedia.org/wiki/External_sorting#External_merge_sort
You can read chunks and do quick sorts on them. Then merge sort all the chunks together at once
def merge( A, B ): # send 2 arrays
if empty( A ):
return B # return B if the other is empty
if empty( B ):
return A
if A[ 0 ] < B[ 0 ]: # if first element in A is smaller, put A array before B array into one array
return concat(
A[ 0 ], merge(
A[ 1...A_n ], B))
else:
return concat(
B[ 0 ], merge(
A, B[ 1...B_n ]))
def mergeSort( A, n ):
if n = 1:
return A # it is already sorted
middle = floor( n / 2 )
leftHalf = A[ 1...middle ]
rightHalf = A[ ( middle + 1 )...n ] # split array in half
return merge(
mergeSort(leftHalf, middle), # split and merge left half
mergeSort(rightHalf, n - middle))