Mergepgids copies the sorted union of a and b into dst. If dst is too small, it panics.
(dst, a, b Pgids)
| 363 | // Mergepgids copies the sorted union of a and b into dst. |
| 364 | // If dst is too small, it panics. |
| 365 | func Mergepgids(dst, a, b Pgids) { |
| 366 | if len(dst) < len(a)+len(b) { |
| 367 | panic(fmt.Errorf("mergepgids bad len %d < %d + %d", len(dst), len(a), len(b))) |
| 368 | } |
| 369 | // Copy in the opposite slice if one is nil. |
| 370 | if len(a) == 0 { |
| 371 | copy(dst, b) |
| 372 | return |
| 373 | } |
| 374 | if len(b) == 0 { |
| 375 | copy(dst, a) |
| 376 | return |
| 377 | } |
| 378 | |
| 379 | // Merged will hold all elements from both lists. |
| 380 | merged := dst[:0] |
| 381 | |
| 382 | // Assign lead to the slice with a lower starting value, follow to the higher value. |
| 383 | lead, follow := a, b |
| 384 | if b[0] < a[0] { |
| 385 | lead, follow = b, a |
| 386 | } |
| 387 | |
| 388 | // Continue while there are elements in the lead. |
| 389 | for len(lead) > 0 { |
| 390 | // Merge largest prefix of lead that is ahead of follow[0]. |
| 391 | n := sort.Search(len(lead), func(i int) bool { return lead[i] > follow[0] }) |
| 392 | merged = append(merged, lead[:n]...) |
| 393 | if n >= len(lead) { |
| 394 | break |
| 395 | } |
| 396 | |
| 397 | // Swap lead and follow. |
| 398 | lead, follow = follow, lead[n:] |
| 399 | } |
| 400 | |
| 401 | // Append what's left in follow. |
| 402 | _ = append(merged, follow...) |
| 403 | } |