76
правок
Изменения
→Пример
| style="background:#FFCC00"| 1 || || || style="background: #77A9F4"| 1 || style="background: #9ACD32"| 3
|-align="center"
| <tex>1 </tex> || style="background:#FFCC00"| 5 || || style="background: #77A9F4"| 5 || style="background: #9ACD32"| 10
|-align="center"
| <tex>1 </tex> || style="background:#FFCC00"| 2 || || style="background: #77A9F4"| 2 || style="background: #9ACD32"| 4
|-align="center"
| <tex>1 </tex> || <tex>2 </tex> || style="background:#FFCC00"| 3 || style="background: #77A9F4"| 3 || style="background: #9ACD32"| 8
|}
| colspan="3"|<tex>B</tex>
|-align="center"
| <tex>3</tex>||<tex>4</tex>||<tex>8</tex>
|}
| ||
| colspan="5"|<tex>C_2^s</tex>
|-align="center"
| <tex>1</tex>||<tex>2</tex>||<tex>5</tex>||<tex>6</tex>||<tex>12</tex>
|}
| ||
| colspan="9"|<tex>\mathtt{merged}</tex>
|-align="center"
|!\pi|<tex>1</tex>||<tex>2</tex>||<tex>3</tex>||<tex>4</tex>||<tex>5</tex>||<tex>6</tex>||<tex>8</tex>||<tex>12</tex>
|-align="center"
|!key|<tex>1</tex>||<tex>2</tex>||<tex>3</tex>||<tex>4</tex>||<tex>5</tex>||<tex>6</tex>||<tex>7</tex>||<tex>8</tex>
|}
|}
| style="background:#FFCC00"| 3 || || || style="background: #77A9F4"| 3
|-align="center"
| <tex>3 </tex> || style="background:#FFCC00"| 4 || || style="background: #77A9F4"| 4
|-align="center"
| <tex>3 </tex> || <tex>4 </tex> || style="background:#FFCC00"| 7 || style="background: #77A9F4"| 7
|}
! <tex>B_1</tex>||<tex>B_2</tex>||<tex>B_3</tex>||<tex>B_4</tex>||<tex>key</tex>||<tex>\pi</tex>
|-align="center"
| style="background:#FFCC00"| 1 || <tex>4 </tex> || <tex>7 </tex> || || style="background: #77A9F4"| 1 || style="background: #9ACD32"| 1
|-align="center"
| <tex>1 </tex> || style="background:#FFCC00"| <tex>2 </tex> || <tex>7 </tex> || || style="background: #77A9F4"| 2 || style="background: #9ACD32"| 2
|-align="center"
| <tex>1 </tex> || <tex>2 </tex> || <tex>7 </tex> || style="background:#FFCC00"| 8 || style="background: #77A9F4"| 8 || style="background: #9ACD32"| 12
|-align="center"
| <tex>1 </tex> || <tex>2 </tex> || style="background:#FFCC00"| 6 || <tex>8 </tex> || style="background: #77A9F4"| 6 || style="background: #9ACD32"| 6
|-align="center"
| <tex>1 </tex> || <tex>2 </tex> || style="background:#FFCC00"| 5 || <tex>8 </tex> || style="background: #77A9F4"| 5 || style="background: #9ACD32"| 5
|}
| colspan="4"|<tex>B</tex>
|-align="center"
| <tex>1</tex>||<tex>2</tex>||<tex>5</tex>||<tex>12</tex>
|}
| ||
| colspan="2"|<tex>C_3^s</tex>
|-align="center"
| <tex>7</tex>||<tex>11</tex>
|}
| ||
| colspan="6"|<tex>\mathtt{merged}</tex>
|-align="center"
|!\pi|<tex>1</tex>||<tex>2</tex>||<tex>5</tex>||<tex>7</tex>||<tex>11</tex>||<tex>12</tex>
|-align="center"
|!key|<tex>1</tex>||<tex>2</tex>||<tex>3</tex>||<tex>4</tex>||<tex>5</tex>||<tex>6</tex>
|}
|}
| style="background:#FFCC00"| 1 || || || || style="background: #77A9F4"| 1
|-align="center"
| <tex>1 </tex> || style="background:#FFCC00"| 2 || || || style="background: #77A9F4"| 2
|-align="center"
| <tex>1 </tex> || <tex>2 </tex> || style="background:#FFCC00"| 3 || || style="background: #77A9F4"| 3
|-align="center"
| <tex>1 </tex> || <tex>2 </tex> || <tex>3 </tex> || style="background:#FFCC00"| 6 || style="background: #77A9F4"| 6
|}
! <tex>B_1</tex>||<tex>B_2</tex>||<tex>B_3</tex>||<tex>B_4</tex>||<tex>B_5</tex>||<tex>key</tex>||<tex>\pi</tex>
|-align="center"
| <tex>1 </tex> || <tex>2 </tex> || <tex>3 </tex> || style="background:#FFCC00"| 4 || || style="background: #77A9F4"| 4 || style="background: #9ACD32"| 7
|-align="center"
| <tex>1 </tex> || <tex>2 </tex> || <tex>3 </tex> || <tex>4 </tex> || style="background:#FFCC00"| 5 || style="background: #77A9F4"| 5 || style="background: #9ACD32"| 11
|}
Результат завершения алгоритма:
Получаем, что длина НВП — <tex>5</tex>, и НВП оканчивается на <tex>\mathtt{merged}[5]=11</tex>.
'''Восстановление НВП'''
! colspan="12"| <tex>\mathtt{predecessor}</tex>
|-align="center"
| style="background:#DCFFFF"|<tex>1</tex>||style="background:#DCDCFF"|<tex>2</tex>||<tex>3</tex>||<tex>4</tex>||style="background:#DCFFDC"|<tex>5</tex>||<tex>6</tex>||style="background:#FFDCDC"|<tex>7</tex>||<tex>8</tex>||<tex>9</tex>||<tex>10</tex>||style="background:#FFFFC8"|<tex>11</tex>||<tex>12</tex>
|-align="center"
|style="background:#FFFFC8"| ||style="background:#DCFFFF"|<tex>1</tex>|| ||<tex>3</tex>||style="background:#DCDCFF"|<tex>2</tex>||style="background:#E6E6FF"|<tex>2</tex>||style="background:#DCFFDC"|<tex>5</tex>||<tex>4</tex>|| ||<tex>3</tex>||style="background:#FFDCDC"|<tex>7</tex>||<tex>8 </tex>
|}
Начинаем восстановление с <tex>\mathtt{merged}[5] = 11</tex>:
{| class="wikitable" style="center"
|-align="center"
| обратный порядок||style="background:#FFFFC8"|<tex>11</tex>||style="background:#FFDCDC"|<tex>7</tex>||style="background:#DCFFDC"|<tex>5</tex>||style="background:#E6E6FF"|<tex>2</tex>||style="background:#DCFFFF"|<tex>1</tex>
|-align="center"
| НВП||style="background:#DCFFFF"|<tex>1</tex>||style="background:#E6E6FF"|<tex>2</tex>||style="background:#DCFFDC"|<tex>5</tex>||style="background:#FFDCDC"|<tex>7</tex>||style="background:#FFFFC8"|<tex>11</tex>
|}
