export type Comparator < T > = ( x : T , y : T ) => number ; /**
 * Sorts an array using merge sort
 */ export function mergeSort < T > ( array , comparatorFn ) { if ( array . length <= 1 ) { return array ; } const middle = Math . floor ( array . length / 2 ) ; const left = array . slice ( 0 , middle ) ; const right = array . slice ( middle ) ; return merge ( mergeSort ( left , comparatorFn ) , mergeSort ( right , comparatorFn ) , comparatorFn ) ; } /** Merge (conquer) step of mergeSort */ function merge < T > ( left , right , comparatorFn ) { const array = [ ] ; let lIndex = 0 ; let rIndex = 0 ; while ( lIndex + rIndex < left . length + right . length ) { const lItem = left [ lIndex ] ; const rItem = right [ rIndex ] ; if ( lItem == null ) { array . push ( rItem ) ; rIndex ++ ; } else if ( rItem == null ) { array . push ( lItem ) ; lIndex ++ ; } else if ( comparatorFn ( lItem , rItem ) < 0 ) { array . push ( lItem ) ; lIndex ++ ; } else { array . push ( rItem ) ; rIndex ++ ; } } return array ; }