@Sampo의 요약을 기반으로 TypeScript에서 솔루션을 작성했습니다. 코드는 아래에서 찾을 수 있습니다.

그 과정에서 몇 가지 통찰력을 얻었습니다.

• 기존의 두 정렬 키 사이 의 중간 에만 삽입 하면 새로운 정렬 키가 필요하며, 교체 (즉, 재 배열)로 인해 분할 (예 : 새로운 중간 점)이 발생 하지 않습니다 . 두 항목을 이동하고 그 중 하나만 터치하면 목록에서 두 요소가 변경된 위치에 대한 정보가 손실됩니다. 시작해야하더라도 좋은 아이디어인지 확인하십시오.

• 1074 : 번째 중간 점 분할마다 부동 소수점 범위를 정규화해야합니다. 우리는 단순히 새로운 중간 점이 불변을 만족시키는 지 확인함으로써 이것을 감지합니다.

  a.sortKey < m && m < b.sortKey

• 정렬 키가 정규화되기 때문에 스케일링은 중요하지 않습니다. 정규화는 여전히 1074중간 지점 분할 마다 발생합니다 . 우리가 처음에 숫자를 더 널리 배포하면 상황이 개선되지 않을 것입니다.

• 정렬 키 정규화는 매우 드 rare니다. 정규화가 눈에 띄지 않는 지점까지이 비용을 상각합니다. 그러나 1000 개가 넘는 요소가있는 경우이 접근법에주의를 기울일 것입니다.

export interface HasSortKey {
  sortKey: number;
}

function normalizeList<T extends HasSortKey>(list: Array<T>) {
  const normalized = new Array<T>(list.length);
  for (let i = 0; i < list.length; i++) {
    normalized[i] = { ...list[i], sortKey: i };
  }
  return normalized;
}

function insertItem<T extends HasSortKey>(
  list: Array<T>,
  index: number,
  item: Partial<T>
): Array<T> {
  if (list.length === 0) {
    list.push({ ...item, sortKey: 0 } as T);
  } else {
    // list is non-empty

    if (index === 0) {
      list.splice(0, 0, { ...item, sortKey: list[0].sortKey - 1 } as T);
    } else if (index < list.length) {
      // midpoint, index is non-zero and less than length

      const a = list[index - 1];
      const b = list[index];

      const m = (a.sortKey + b.sortKey) / 2;

      if (!(a.sortKey < m && m < b.sortKey)) {
        return insertItem(normalizeList(list), index, item);
      }

      list.splice(index, 0, { ...item, sortKey: m } as T);
    } else if (index === list.length) {
      list.push({ ...item, sortKey: list[list.length - 1].sortKey + 1 } as T);
    }
  }
  return list;
}

export function main() {
  const normalized: Array<number> = [];

  let list: Array<{ n: number } & HasSortKey> = [];

  list = insertItem(list, 0, { n: 0 });

  for (let n = 1; n < 10 * 1000; n++) {
    const list2 = insertItem(list, 1, { n });
    if (list2 !== list) {
      normalized.push(n);
    }
    list = list2;
  }

  let m = normalized[0];

  console.log(
    normalized.slice(1).map(n => {
      const k = n - m;
      m = n;
      return k;
    })
  );
}

답변