Chia để trị (Divide and Conquer)

def merge_sort(arr):
    if len(arr) <= 1:
        return arr
    
    mid = len(arr) // 2
    left = merge_sort(arr[:mid])
    right = merge_sort(arr[mid:])
    
    return merge(left, right)
 
def merge(left, right):
    result = []
    i = j = 0
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            result.append(left[i])
            i += 1
        else:
            result.append(right[j])
            j += 1
    result.extend(left[i:])
    result.extend(right[j:])
    return result

fun mergeSort(arr: List<Int>): List<Int> {
    if (arr.size <= 1) return arr
    
    val mid = arr.size / 2
    val left = mergeSort(arr.subList(0, mid))
    val right = mergeSort(arr.subList(mid, arr.size))
    
    return merge(left, right)
}
 
fun merge(left: List<Int>, right: List<Int>): List<Int> {
    val result = mutableListOf<Int>()
    var i = 0; var j = 0
    while (i < left.size && j < right.size) {
        if (left[i] <= right[j]) result.add(left[i++])
        else result.add(right[j++])
    }
    result.addAll(left.subList(i, left.size))
    result.addAll(right.subList(j, right.size))
    return result
}

List<int> mergeSort(List<int> arr) {
  if (arr.length <= 1) return arr;
  
  int mid = arr.length ~/ 2;
  List<int> left = mergeSort(arr.sublist(0, mid));
  List<int> right = mergeSort(arr.sublist(mid));
  
  return merge(left, right);
}
 
List<int> merge(List<int> left, List<int> right) {
  List<int> result = [];
  int i = 0, j = 0;
  while (i < left.length && j < right.length) {
    if (left[i] <= right[j]) result.add(left[i++]);
    else result.add(right[j++]);
  }
  result.addAll(left.sublist(i));
  result.addAll(right.sublist(j));
  return result;
}

func mergeSort(_ arr: [Int]) -> [Int] {
    if arr.count <= 1 { return arr }
    
    let mid = arr.count / 2
    let left = mergeSort(Array(arr[0..<mid]))
    let right = mergeSort(Array(arr[mid...]))
    
    return merge(left, right)
}
 
func merge(_ left: [Int], _ right: [Int]) -> [Int] {
    var result = [Int]()
    var i = 0, j = 0
    while i < left.count && j < right.count {
        if left[i] <= right[j] { result.append(left[i]); i += 1 }
        else { result.append(right[j]); j += 1 }
    }
    return result + left[i...] + right[j...]
}

int[] mergeSort(int[] arr) {
    if (arr.length <= 1) return arr;
    
    int mid = arr.length / 2;
    int[] left = mergeSort(Arrays.copyOfRange(arr, 0, mid));
    int[] right = mergeSort(Arrays.copyOfRange(arr, mid, arr.length));
    
    return merge(left, right);
}
 
int[] merge(int[] left, int[] right) {
    int[] result = new int[left.length + right.length];
    int i = 0, j = 0, k = 0;
    while (i < left.length && j < right.length) {
        if (left[i] <= right[j]) result[k++] = left[i++];
        else result[k++] = right[j++];
    }
    while (i < left.length) result[k++] = left[i++];
    while (j < right.length) result[k++] = right[j++];
    return result;
}

def power(base, exp):
    """Tính base^exp trong O(log n)"""
    if exp == 0:
        return 1
    half = power(base, exp // 2)
    if exp % 2 == 0:
        return half * half
    else:
        return half * half * base

fun power(base: Long, exp: Int): Long {
    if (exp == 0) return 1
    val half = power(base, exp / 2)
    return if (exp % 2 == 0) half * half
           else half * half * base
}

int power(int base, int exp) {
  if (exp == 0) return 1;
  int half = power(base, exp ~/ 2);
  if (exp % 2 == 0) return half * half;
  else return half * half * base;
}

func power(_ base: Int, _ exp: Int) -> Int {
    if exp == 0 { return 1 }
    let half = power(base, exp / 2)
    if exp % 2 == 0 { return half * half }
    else { return half * half * base }
}

long power(long base, int exp) {
    if (exp == 0) return 1;
    long half = power(base, exp / 2);
    if (exp % 2 == 0) return half * half;
    else return half * half * base;
}