3-Way Merge Sort — VisualAlgorithms Docs

How it works

Splits into three parts instead of two. Slightly fewer comparisons than standard merge sort in theory.
Implementation

      
 function merge3Sort(arr, stats) {
  const n = arr.length;
  function merge3Way(lo, mid1, mid2, hi) {
    const merged = [];
    let i = lo, j = mid1, k = mid2;
    while (i < mid1 && j < mid2 && k < hi) {
      compare(i, j);
      let pick;
      if (arr[i] <= arr[j]) {
        compare(i, k);
        if (arr[i] <= arr[k]) pick = i; else pick = k;
      } else {
        compare(j, k);
        if (arr[j] <= arr[k]) pick = j; else pick = k;
      }
      if (pick === i) merged.push(arr[i++]); else if (pick === j) merged.push(arr[j++]); else merged.push(arr[k++]);
    }
    while (i < mid1 && j < mid2) {
      compare(i, j);
      if (arr[i] <= arr[j]) merged.push(arr[i++]); else merged.push(arr[j++]);
    }
    while (i < mid1 && k < hi) {
      compare(i, k);
      if (arr[i] <= arr[k]) merged.push(arr[i++]); else merged.push(arr[k++]);
    }
    while (j < mid2 && k < hi) {
      compare(j, k);
      if (arr[j] <= arr[k]) merged.push(arr[j++]); else merged.push(arr[k++]);
    }
    while (i < mid1) merged.push(arr[i++]);
    while (j < mid2) merged.push(arr[j++]);
    while (k < hi) merged.push(arr[k++]);
    for (let p = 0; p < merged.length; p++) {
      arr[lo + p] = merged[p];
      write(lo + p, merged[p]);
    }
  }
  function sort3(lo, hi) {
    if (hi - lo < 2) return;
    const third = Math.max(1, Math.floor((hi - lo) / 3));
    const mid1 = lo + third;
    const mid2 = lo + 2 * third;
    sort3(lo, mid1);
    sort3(mid1, mid2);
    sort3(mid2, hi);
    merge3Way(lo, mid1, mid2, hi);
    checkpoint(lo, n);
  }
  sort3(0, n);
}
 def merge3Sort(arr, stats):
    def merge3Way(lo, mid1, mid2, hi):
        merged = []
        i = lo
        j = mid1
        k = mid2
        while (((i < mid1) and (j < mid2)) and (k < hi)):
            compare(i, j)
            pick = None
            if (arr[i] <= arr[j]):
                compare(i, k)
                if (arr[i] <= arr[k]):
                    pick = i
                else:
                    pick = k
            else:
                compare(j, k)
                if (arr[j] <= arr[k]):
                    pick = j
                else:
                    pick = k
            if (pick == i):
                merged.append(arr[((i := i + 1) - 1)])
            elif (pick == j):
                merged.append(arr[((j := j + 1) - 1)])
            else:
                merged.append(arr[((k := k + 1) - 1)])
        while ((i < mid1) and (j < mid2)):
            compare(i, j)
            if (arr[i] <= arr[j]):
                merged.append(arr[((i := i + 1) - 1)])
            else:
                merged.append(arr[((j := j + 1) - 1)])
        while ((i < mid1) and (k < hi)):
            compare(i, k)
            if (arr[i] <= arr[k]):
                merged.append(arr[((i := i + 1) - 1)])
            else:
                merged.append(arr[((k := k + 1) - 1)])
        while ((j < mid2) and (k < hi)):
            compare(j, k)
            if (arr[j] <= arr[k]):
                merged.append(arr[((j := j + 1) - 1)])
            else:
                merged.append(arr[((k := k + 1) - 1)])
        while (i < mid1):
            merged.append(arr[((i := i + 1) - 1)])
        while (j < mid2):
            merged.append(arr[((j := j + 1) - 1)])
        while (k < hi):
            merged.append(arr[((k := k + 1) - 1)])
        for p in range(len(merged)):
            arr[(lo + p)] = merged[p]
            write((lo + p), merged[p])

    def sort3(lo, hi):
        if ((hi - lo) < 2):
            return
        third = (1 if 1 >= ((hi - lo) // 3) else ((hi - lo) // 3))
        mid1 = (lo + third)
        mid2 = (lo + (2 * third))
        sort3(lo, mid1)
        sort3(mid1, mid2)
        sort3(mid2, hi)
        merge3Way(lo, mid1, mid2, hi)
        checkpoint(lo, n)

    sort3(0, n)
 #include <vector>
#include <algorithm>
void merge3Way(int lo, int mid1, int mid2, int hi);
void sort3(int lo, int hi);

void merge3Way(int lo, int mid1, int mid2, int hi) {
    std::vector<int> merged;
    int i = lo;
    int j = mid1;
    int k = mid2;
    while((((i < mid1) && (j < mid2)) && (k < hi))) {
        compare(i, j);
        int pick;
        if((arr[i] <= arr[j])) {
            compare(i, k);
            if((arr[i] <= arr[k])) {
                pick = i;
            } else {
                pick = k;
            }
        } else {
            compare(j, k);
            if((arr[j] <= arr[k])) {
                pick = j;
            } else {
                pick = k;
            }
        }
        if((pick == i)) {
            merged.push_back(arr[i++]);
        } else if((pick == j)) {
            merged.push_back(arr[j++]);
        } else {
            merged.push_back(arr[k++]);
        }
    }
    while(((i < mid1) && (j < mid2))) {
        compare(i, j);
        if((arr[i] <= arr[j])) {
            merged.push_back(arr[i++]);
        } else {
            merged.push_back(arr[j++]);
        }
    }
    while(((i < mid1) && (k < hi))) {
        compare(i, k);
        if((arr[i] <= arr[k])) {
            merged.push_back(arr[i++]);
        } else {
            merged.push_back(arr[k++]);
        }
    }
    while(((j < mid2) && (k < hi))) {
        compare(j, k);
        if((arr[j] <= arr[k])) {
            merged.push_back(arr[j++]);
        } else {
            merged.push_back(arr[k++]);
        }
    }
    while((i < mid1)) {
        merged.push_back(arr[i++]);
    }
    while((j < mid2)) {
        merged.push_back(arr[j++]);
    }
    while((k < hi)) {
        merged.push_back(arr[k++]);
    }
    for(int p=0; p<(int)merged.size(); p++) {
        arr[(lo + p)] = merged[p];
        write((lo + p), merged[p]);
    }
}

void sort3(int lo, int hi) {
    if(((hi - lo) < 2)) {
        return;
    }
    int third = ((1) > (((hi - lo) / 3)) ? (1) : (((hi - lo) / 3)));
    int mid1 = (lo + third);
    int mid2 = (lo + (2 * third));
    sort3(lo, mid1);
    sort3(mid1, mid2);
    sort3(mid2, hi);
    merge3Way(lo, mid1, mid2, hi);
    checkpoint(lo, n);
}

void sort(std::vector<int>& arr, int n, int& comparisons, int& swaps) {
    sort3(0, n);
} void merge3Way(int lo, int mid1, int mid2, int hi) {
    var merged = new List<int>();
    int i = lo;
    int j = mid1;
    int k = mid2;
    while((((i < mid1) && (j < mid2)) && (k < hi))) {
        compare(i, j);
        int pick;
        if((arr[i] <= arr[j])) {
            compare(i, k);
            if((arr[i] <= arr[k])) {
                pick = i;
            } else {
                pick = k;
            }
        } else {
            compare(j, k);
            if((arr[j] <= arr[k])) {
                pick = j;
            } else {
                pick = k;
            }
        }
        if((pick == i)) {
            merged.Add(arr[i++]);
        } else if((pick == j)) {
            merged.Add(arr[j++]);
        } else {
            merged.Add(arr[k++]);
        }
    }
    while(((i < mid1) && (j < mid2))) {
        compare(i, j);
        if((arr[i] <= arr[j])) {
            merged.Add(arr[i++]);
        } else {
            merged.Add(arr[j++]);
        }
    }
    while(((i < mid1) && (k < hi))) {
        compare(i, k);
        if((arr[i] <= arr[k])) {
            merged.Add(arr[i++]);
        } else {
            merged.Add(arr[k++]);
        }
    }
    while(((j < mid2) && (k < hi))) {
        compare(j, k);
        if((arr[j] <= arr[k])) {
            merged.Add(arr[j++]);
        } else {
            merged.Add(arr[k++]);
        }
    }
    while((i < mid1)) {
        merged.Add(arr[i++]);
    }
    while((j < mid2)) {
        merged.Add(arr[j++]);
    }
    while((k < hi)) {
        merged.Add(arr[k++]);
    }
    for(int p=0; p<merged.Count; p++) {
        arr[(lo + p)] = merged[p];
        write((lo + p), merged[p]);
    }
}

void sort3(int lo, int hi) {
    if(((hi - lo) < 2)) {
        return;
    }
    int third = Math.Max(1, ((hi - lo) / 3));
    int mid1 = (lo + third);
    int mid2 = (lo + (2 * third));
    sort3(lo, mid1);
    sort3(mid1, mid2);
    sort3(mid2, hi);
    merge3Way(lo, mid1, mid2, hi);
    checkpoint(lo, n);
}

public void Sort(int[] arr, int n, dynamic stats) {
    sort3(0, n);
} #include <stdio.h>
#include <stdlib.h>
void merge3Way(int lo, int mid1, int mid2, int hi);
void sort3(int lo, int hi);

void merge3Way(int lo, int mid1, int mid2, int hi) {
    int* merged = (int*)malloc(n * sizeof(int)); int merged_len = 0;
    int i = lo;
    int j = mid1;
    int k = mid2;
    while((((i < mid1) && (j < mid2)) && (k < hi))) {
        compare(i, j);
        int pick;
        if((arr[i] <= arr[j])) {
            compare(i, k);
            if((arr[i] <= arr[k])) {
                pick = i;
            } else {
                pick = k;
            }
        } else {
            compare(j, k);
            if((arr[j] <= arr[k])) {
                pick = j;
            } else {
                pick = k;
            }
        }
        if((pick == i)) {
            merged[merged_len++] = arr[i++];
        } else if((pick == j)) {
            merged[merged_len++] = arr[j++];
        } else {
            merged[merged_len++] = arr[k++];
        }
    }
    while(((i < mid1) && (j < mid2))) {
        compare(i, j);
        if((arr[i] <= arr[j])) {
            merged[merged_len++] = arr[i++];
        } else {
            merged[merged_len++] = arr[j++];
        }
    }
    while(((i < mid1) && (k < hi))) {
        compare(i, k);
        if((arr[i] <= arr[k])) {
            merged[merged_len++] = arr[i++];
        } else {
            merged[merged_len++] = arr[k++];
        }
    }
    while(((j < mid2) && (k < hi))) {
        compare(j, k);
        if((arr[j] <= arr[k])) {
            merged[merged_len++] = arr[j++];
        } else {
            merged[merged_len++] = arr[k++];
        }
    }
    while((i < mid1)) {
        merged[merged_len++] = arr[i++];
    }
    while((j < mid2)) {
        merged[merged_len++] = arr[j++];
    }
    while((k < hi)) {
        merged[merged_len++] = arr[k++];
    }
    for(int p=0; p<merged_len; p++) {
        arr[(lo + p)] = merged[p];
        write((lo + p), merged[p]);
    }
}

void sort3(int lo, int hi) {
    if(((hi - lo) < 2)) {
        return;
    }
    int third = ((1) > (((hi - lo) / 3)) ? (1) : (((hi - lo) / 3)));
    int mid1 = (lo + third);
    int mid2 = (lo + (2 * third));
    sort3(lo, mid1);
    sort3(mid1, mid2);
    sort3(mid2, hi);
    merge3Way(lo, mid1, mid2, hi);
    checkpoint(lo, n);
}

void sort(int arr[], int n, int* comparisons, int* swaps) {
    sort3(0, n);
} 