Added span

Combinations.cs

using System;
using System.Collections.Generic;
using System.IO;
using System.Linq;
using System.Runtime.ConstrainedExecution;
using System.Runtime.InteropServices;
using System.Security;
using System.Text;
using System.Threading;
using System.Threading.Tasks;

namespace ConsoleApp
{
    class Program
    {
        private const int DataSize = 8000;
        private const int DataItemSize = 20;

        static void Main(string[] args)
        {

            var comparer = StringComparer.Ordinal;

            var data = PrepareData(comparer);
            var result = new List<ResultItem>(DataSize * DataSize / 2);

            const int firstIndex = 0;
            const int lastIndex = DataItemSize - 1;

            for (int leftIndex = 0; leftIndex < DataSize - 1; leftIndex++)
            {
                var boundsExceed = false;
                for (int rightIndex = leftIndex + 1; rightIndex < DataSize; rightIndex++)
                {
                    var resultItem = new ResultItem(leftIndex, rightIndex);
                    var left = data[leftIndex];
                    var right = data[rightIndex];


                    if (boundsExceed)
                    {
                        resultItem.Items = Array.Empty<string>();
                        result.Add(resultItem);
                        continue;
                    }

                    //hot path
                    var boundComp = comparer.Compare(left[lastIndex], right[firstIndex]);
                    if (boundComp < 0)
                    {
                        resultItem.Items = Array.Empty<string>();
                        result.Add(resultItem);
                        boundsExceed = true;
                        continue;
                    }
                    if (boundComp == 0)
                    {
                        resultItem.Items = new[] { right[firstIndex] };
                        result.Add(resultItem);
                        continue;
                    }

                    //main comparison

                    var startLeft = Array.BinarySearch(left, right[firstIndex], comparer);
                    if (startLeft < 0)
                        startLeft = ~startLeft;

                    var endRight = Array.BinarySearch(right, left[lastIndex], comparer);
                    if (endRight < 0)
                    {
                        endRight = Math.Min(~endRight, lastIndex);
                    }


                    var items = new List<string>();
                    var startRight = 0;

                    while (startLeft < DataItemSize && startRight <= endRight)
                    {
                        var cmp = comparer.Compare(left[startLeft], right[startRight]);
                        if (cmp < 0)
                        {
                            startLeft++;
                        }
                        else if (cmp > 0)
                        {
                            startRight++;
                        }
                        else
                        {
                            items.Add(left[startLeft]);
                            startLeft++;
                            startRight++;
                        }
                    }

                    resultItem.Items = items.ToArray();
                    result.Add(resultItem);
                }
            }

            var r = result.Where(p => p.Items.Length > 0).ToArray();

            Console.Write(r);

        }

        public static string[][] PrepareData(StringComparer comparer)
        {
            //prepare data
            var data = new string[DataSize][];
            for (int i = 0; i < DataSize; i++)
            {
                data[i] = new string[DataItemSize];
                for (int j = 0; j < DataItemSize; j++)
                    data[i][j] = RandomString(6);
            }

            //sort
            for (int i = 0; i < DataSize / 2; i++)
                Array.Sort(data[i], comparer);

            //again sort 
            Array.Sort(data, (l, r) => comparer.Compare(l[0], r[0]));
            return data;
        }

        public struct ResultItem
        {
            public int LeftIndex;

            public int RightIndex;

            public string[] Items;

            public ResultItem(int leftIndex, int rightIndex)
            {
                LeftIndex = leftIndex;
                RightIndex = rightIndex;
                Items = Array.Empty<string>();
            }
        }

        private static readonly Random random = new Random();
        public static string RandomString(int length)
        {
            const string chars = "ABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789";

            Span<char> sb = stackalloc char[20];
            for (int i = 0; i < length; i++)
            {
                sb[i] = chars[random.Next(chars.Length)];
            }

            return sb.ToString();
        }
    }
}